전설적인 인천 식료품가게의 주인인 김인천 씨는 대대적인 할인행사를 계획하고 있습니다. 계산을 단순하게하기 위해 그는 25% 할인된 가격으로 상점의 모든 품목을 판매하기로 결정했습니다. 즉, 각 품목의 판매 가격은 정상 가격의 정확히 75 %입니다. 우연하게도 인천 식료품가게에서 판매하는 모든 물건의 정상가는 4의 배수인 정수이고, 할인된 가격 역시 편리하게도 모두 정수입니다.
김인천씨는 이 할인행사를 준비하기위해서 먼저 모든 판매물품의 할인된 판매가격을 프린터로 출력을 실행했고, 또한 할인행사 종료후 다시 쓸 모든 품목에 정상가격표 역시 출력을 실행하였습니다.
손님이 찾아와 잠깐 자리를 비웠던 김인천씨가 다시 가격표의 출력을 확인하기 위해서 프린터로 돌아와보니, 공교롭게 프린터는 모든 물품의 할인가격과 정상가격을 따로 구분하지 않고 오름차순으로 정렬한 뒤 순서대로 출력하여 하나의 출력물 더미를 만들었습니다. 각 품목의 할인가격표와 정상가격표 모두가 출력물 더미의 어딘가에 있습니다. 그러나 두 유형(할인가격, 정상가격)의 가격표는 비슷하게 보이고, 모든 품목의 가격을 기억하지 못하기 때문에 김인천씨는 어느 가격표가 할인가격표인지 확신할 수 없습니다. 이 상황에서 김인천씨는 무엇이 할인가격표인지 구분해낼 수 있을까요?
예를 들어, 정상가격이 20, 80, 100 인 경우 할인가격은 15, 60, 75이며 프린터의 인쇄출력더미는 오름차순으로 정렬된 15, 20, 60, 75, 80, 100 가격표들로 구성됩니다.
입력
입력의 첫 번째 라인(줄)은 테스트 사례의 케이스의 수 T를 나타냅니다. 이후의 라인은 T개의 테스트 케이스가 이어집니다. 각 테스트 케이스는 두 줄로 구성됩니다. 첫 번째 줄에는 INU 식료품가게에 존재하는 상품수인 단일 정수 N이 포함됩니다. 두 번째 줄에는 프린터에서 가격의 오름차순으로 인쇄한 2N개의 정수 P1, P2, …, P2N이 주어집니다.
입력값의 제한은 아래와 같습니다
1 ≤ T ≤ 100.
모든 i에 대해서 1 ≤ Pi ≤ 109.
모든 i에 대해서 Pi ≤ Pi+1. (가격은 오름차순으로 존재)
정답은 단 하나만 존재하는것이 보장되어 있음.
1 ≤ N ≤ 100
출력
개별 테스트 케이스에 대해서 출력라인은 “Case #x: y” 형식(큰 따옴표는 제외)으로 출력하며, x는 1부터 시작하는 테스트 케이스의 번호 (인덱스)이며, y는 할인가격에 해당하는 오름차순으로 정렬된 N개의 정수들이다.
예제 입력 1
1 2 3 4 5
2 3 15 20 60 75 80 100 4 9 9 12 12 12 15 16 20
예제 출력 1
1 2
Case #1: 15 60 75 Case #2: 9 9 12 15
힌트
예제의 첫 번째 테스트 케이스인 Case #1은 문제에서 예로들어서 설명한 세 개의 물품에 대한 정상가격과 할인가격 6개입니다. 또한 예제의 Case #2에서는 여러 품목이 동일한 가격을 가질 수 있고, 어떤 품목의 할인가격이 다른 품목 정상가격과 같을 수도 있습니다.
세훈이는 선물가게를 운영한다. 세훈이의 선물가게는 특이하게도 손님이 어떤 선물을 구매할지 선택할 수가 없다. 대신 세훈이의 취향으로 랜덤하게 준비된 선물 중 몇 개를 구매할 것인지, 파란색과 빨간색 중 어떤 색으로 포장 받을 것인지만 결정해 주문할 수 있다.
상민이와 지수는 세훈이의 가게에서 선물 포장을 맡은 아르바이트생이다. 손님들은 파란색 포장지를 원하면 상민이에게, 빨간색 포장지를 원하면 지수에게 주문을 한다. 두 사람은 각자 주문을 받으면 그때부터 포장을 시작하는데, 현재 남아있는 선물 중 가장 앞에 있는 선물을 가져와 포장하고 주문을 받은 개수만큼 이를 반복하는 형태다. 이때 선물 하나를 포장하는 데 상민이는 A초, 지수는 B초가 걸린다. 두 사람 모두 받거나 밀린 주문이 없는데 미리 선물을 가져오거나 포장하는 일은 없으며, 두 사람이 동시에 선물을 가져올 때는 알바짬이 조금 더 있는 상민이가 먼저 가져오고, 지수가 그 뒤의 선물을 가져온다.
세훈이는 어제 구매한 선물이 망가져 있다는 항의 전화를 받았다. 자신이 준비한 선물에는 문제가 없었기에 손님에게 포장지의 색을 물었지만, 손님은 자신이 받은 선물이 무엇인지만 말하며 화를 낼 뿐이었다. 어쩔 수 없이 세훈이는 어제 가게를 방문한 손님들의 주문 내역을 보고 그 선물을 누가 포장했는지 파악하려 한다.
방문한 손님의 수와 각 손님이 주문한 시각, 선택한 포장지, 포장 받을 선물의 개수가 주어졌을 때 상민이와 지수가 각자 어떤 선물들을 포장했는지 알아내는 프로그램을 작성해보자.
입력
첫 줄에 상민이가 선물 하나를 포장하는 데 걸리는 시간 A, 지수가 선물 하나를 포장하는 데 걸리는 시간 B, 어제 세훈이 가게의 손님 수 N(1 ≤ N ≤ 1,000)이 주어진다.
이후 N개의 줄에 걸쳐 1번부터 N번 손님의 주문 시각 ti(1 ≤ ti ≤ 86,400), 선택한 포장지의 색깔 ci(ci = “B”|”R”), 주문한 선물의 개수 mi(1 ≤ mi ≤ 100)가 주어진다.
ti는 가게가 오픈한 지 ti초 후에 손님이 주문했음을 뜻하며 ci는 포장지의 색깔을 의미하는 알파벳으로 “B”는 파란색을, “R”은 빨간색을 의미한다. 주어지는 입력은 시간의 흐름에 맞게 ti의 오름차순으로 주어지며, 서로 같은 시간에 주문한 손님은 없다.
출력
첫 번째 줄에 상민이가 포장한 선물의 개수를 출력한다. 이후 두 번째 줄에 상민이가 포장한 선물들의 번호를 오름차순으로 공백으로 구분하여 출력한다.
세 번째 줄에 지수가 포장한 선물의 개수를 출력한다. 이후 네 번째 줄에 지수가 포장한 선물들의 번호를 오름차순으로 공백으로 구분하여 출력한다.
서브태스크 1 (100점)
A = B = 0
A, B가 0이라는 것은 해당 아르바이트생의 포장 속도가 너무 빨라서, 주문과 동시에 해당 주문의 모든 선물 포장이 끝난다는 의미이다.
for i inrange(int(present_count)): # 주문 개수만큼 반복 heapq.heappush(pacakage_list, [start_time, 'B']) # 상민 포장시작 시간 리스트에 저장 start_time += s_time # 기존 포장시작시간에 포장에 걸리는 시간 더하기 s_end = start_time # 포장끝난 시간은 포장시작시간+포장에 걸리는 시간
elif color == 'R': # 지수 start_time = max(start_time, j_end)
for i inrange(int(present_count)): heapq.heappush(pacakage_list, [start_time, 'R']) start_time += j_time j_end = start_time
s_present, j_present = [], [] # 상민, 지수가 포장한 선물리스트
for i inrange(1, len(pacakage_list) + 1): present = heapq.heappop(pacakage_list) if present[1] == 'B': s_present.append(i) else: j_present.append(i)
if color == 'B': # 상민 start_time = max(start_time, s_end) # if start_time < s_end: # 상민 포장 주문시각이 포장끝난 시각보다 먼저일 경우 # start_time = s_end # 주문시각(포장시작시각)을 포장끝난 시점으로 변경해준다.
for i inrange(int(present_count)): # 주문 개수만큼 반복 sangmin.append([start_time, 'B']) # 상민 포장시작 시간 리스트에 저장 start_time += s_time # 기존 포장시작시간에 포장에 걸리는 시간 더하기 s_end = start_time # 포장끝난 시간은 포장시작시간+포장에 걸리는 시간
elif color == 'R': # 지수 start_time = max(start_time, j_end) # if start_time < j_end: # start_time = j_end
for i inrange(int(present_count)): jisu.append([start_time, 'R']) start_time += j_time j_end = start_time
자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 이 섬에 사는 앵무새들은 놀라울 정도로 인간의 말을 흉내 내는 데 뛰어나다는 것이다. 그들은 서로 떨어져 섬을 탐험하기로 하였으며, 필요하다면 앵무새를 이용해 서로에게 연락하기로 약속하였다.
1개월 후, pps789는 섬의 비밀을 밝힐 결정적인 증거를 찾게 된다. 그는 이 세기의 대발견을 cseteram에게 공유하고자 하였으나, 그의 발견은 방대하여 앵무새 한 마리가 기억하기에는 너무 많은 양이었다. 그렇기 에 pps789는 앵무새 한 마리 대신 앵무새 N마리를 이용하여 자신의 발견을 기록하였으며, 이 앵무새들을 cseteram을 향해 날렸다.
한편 섬의 반대편에서 탐험을 계속하던 cseteram은 앵무새 N마리가 자신에게 날아와 각자 할 말을 하는 것을 보고 당황하였다. pps789가 긴 글을 전달하고 싶었던 것은 알아차렸지만, 각각의 앵무새들이 말하는 것을 차례대로 기록하다 보니 원문이 무엇인지 알 수 없을 정도로 단어의 순서가 엉켜버린 것이다. 대신 그는 관찰을 통해 몇 가지 규칙을 발견할 수 있었다.
한 앵무새는 한 문장을 기억하고 있다. 문장은 여러 단어로 이루어져 있는데, 앵무새는 이 단어들을 순서대로 말한다.
한 앵무새가 단어를 말하고 그다음 단어를 말하기 전에는 약간의 간격이 있는데, 이때 다른 앵무새가 말을 가로채고 자신의 문장을 말할 수 있다.
한 앵무새가 단어를 말하는 도중에는, 다른 앵무새가 말을 가로채지 않는다.
어떤 단어도 앵무새가 말하는 모든 문장을 통틀어 2번 이상 등장하지 않는다.
앵무새는 자신이 기억하고 있는 문장을 끝까지 말한 다음 pps789에게 돌아가며, cseteram은 모든 앵무새가 돌아갈 때 까지 단어를 받아적는다. pps789가 각각의 앵무새들에게 전달한 문장 Si와, cseteram이 받아 적은 문장 L이 주어진다. 이때 문장 L이 위 규칙들을 이용하여 나올 수 있는 문장인지 판별하시오.
입력
첫 번째 줄에 앵무새의 수 N (1 ≤ N ≤ 100) 이 주어진다.
두 번째 줄부터 N개의 줄에 걸쳐 각 앵무새가 말한 문장 Si (1 ≤ i ≤ N) 가 주어지는데, 각 문장을 이루는 단어는 스페이스 한 칸을 구분으로 하여 주어진다. 문장 Si를 이루는 단어의 수는 1개 이상 100개 이하이며, 각 단어는 1개 이상 32개 이하의 영문 소문자로 구성되어있다.
N + 2 번째 줄에는 cseteram이 받아 적은 문장 L이 주어진다. 문장 L을 이루는 단어의 수는 1개 이상 10000개 이하이며, 각 단어는 1개 이상 32개 이하의 영문 소문자로 구성된다.
출력
문장 L이 가능한 문장이라면 Possible을, 불가능한 문장이라면 Impossible을 출력한다.
예제 입력 1
1 2 3 4 5
3 i want to see you next week good luck i want next good luck week to see you
예제 출력 1
1
Possible
예제 입력 2
1 2 3 4
2 i found an interesting cave i found an cave interesting
N = int(input()) parrot = [deque(input().rstrip().split()) for _ inrange(N)]
L = input().rstrip().split() Removed = [] for word in L: for i inrange(N): if parrot[i] and word == parrot[i][0]: parrot[i].popleft() Removed.append(word) break
for i inrange(N): if parrot[i]: print("Impossible") exit() if L != Removed: print("Impossible") else: print("Possible")
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다.
N이 주어졌을 때, 버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다.
출력
첫째 줄에 버리는 카드들을 순서대로 출력한다. 제일 마지막에는 남게 되는 카드의 번호를 출력한다.
크게 낙담한 승현이는 노력해 보았지만, 대부분이 부러져 버려 단 한 부분만 재사용할 수 있다는 것을 깨닫게 되었습니다.
1
)))()
승현이는 이 괄호열을 가지고 놀려고 했으나 올바른 괄호열이 아니기 때문에 행복하지 않았습니다. 이를 보던 지학이는 승현이에게 “그러면 앞과 뒤에 적절하게 괄호를 붙이면 올바른 괄호열이 되지 않을까?”라고 했고, 승현이는 조금 생각한 뒤 그렇게 하기로 했습니다. 예를 들어, 위의 올바르지 않은 괄호열의 경우 앞에 여는 괄호 3개를 붙이면 올바른 괄호열이 됩니다.
1
((()))()
그러나 괄호열을 사서 붙이는 데에는 돈이 들고 많이 붙일수록 놀기가 불편해지기 때문에, 승현이는 가능한 한 괄호열을 적게 추가하려고 합니다.
승현이가 망가뜨리고 사용 가능한 올바르지 않은 괄호열이 주어질 때, 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 구하는 프로그램을 작성하세요.
입력
첫 번째 줄에 올바르지 않은 괄호열 S가 주어집니다. S의 길이는 1 이상 50 이하입니다.
출력
첫 번째 줄에 S를 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 출력합니다. 불가능한 경우는 주어지지 않습니다.
성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이다. 다행히 과제 제출 기한은 학기가 끝날 때까지이다. 너무나도 많은 과제를 하다가 미쳐버린 성애는 아래와 같은 규칙으로 과제를 해 나가고 있다.
과제는 가장 최근에 나온 순서대로 한다. 또한 과제를 받으면 바로 시작한다.
과제를 하던 도중 새로운 과제가 나온다면, 하던 과제를 중단하고 새로운 과제를 진행한다.
새로운 과제가 끝났다면, 이전에 하던 과제를 이전에 하던 부분부터 이어서 한다. (성애는 기억력이 좋기 때문에 아무리 긴 시간이 지나도 본인이 하던 부분을 기억할 수 있다.)
성애는 과제를 받자마자 이 과제가 몇 분이 걸릴지 정확하게 알 수 있고, 성애가 제출한 과제는 무조건 만점을 받는다.
성애는 이번 학기에 자기가 받을 과제 점수를 예상해보고 싶다. 하지만 과제 점수를 예상하는 지금도 과제가 추가되고 있기에 여유를 부릴 수가 없다. 여러분이 성애가 받을 과제 점수를 구해주자!
입력
첫째 줄에 이번 학기가 몇 분인지를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
두번째 줄부터 N줄 동안은 학기가 시작하고 N분째에 주어진 과제의 정보가 아래의 두 경우 중 하나로 주어진다.
1 A T: 과제의 만점은 A점이고, 성애가 이 과제를 해결하는데 T분이 걸린다. A와 T는 모두 정수이다. (1 ≤ A ≤ 100, 1 ≤ T ≤ 1,000,000)
0: 해당 시점에는 과제가 주어지지 않았다.
출력
성애가 받을 과제 점수를 출력한다.
예제 입력 1
1 2 3 4
3 1 100 3 0 0
예제 출력 1
1
100
1분째: 100점짜리 과제 1이 주어지고 이 과제를 하는데 3분이 걸린다. 과제를 받자마자 시작했으므로 과제 1이 끝나는데는 이제 2분 남았다.
2분째: 새로운 과제가 주어지지 않았으므로 과제 1을 이어서 한다.
3분째: 새로운 과제가 주어지지 않았으므로 과제 1을 이어서 한다. 이 시점에 과제 1이 끝나서 100점을 획득한다.
예제 입력 2
1 2 3 4 5 6
5 1 10 3 0 1 100 2 1 20 1 0
예제 출력 2
1
120
1분째 : 과제 1이 나왔고, 받자마자 바로 시작했으므로 과제 1이 끝나기까지 2분 남았다.
2분째 : 새로운 과제가 나오지 않았으므로 과제 1을 이어서 한다.
3분째 : 과제 2가 나왔고, 받자마자 바로 시작했으므로, 과제 2가 끝나기까지 1분 남았다.
4분째 : 과제 3이 나왔고, 받자마자 바로 시작했으므로, 과제 3을 끝내서 20점을 얻는다.
5분째 : 새로운 과제가 나오지 않았으므로 이전에 하던 과제 2를 이어서 하고, 과제 2를 끝내서 100점을 얻는다.
for i inrange(N): sentence = list(input().rstrip().split()) result = [] while sentence: result.append(sentence.pop()) print('Case #{0}: {1}'.format(i + 1, ' '.join(result)))
아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 6, 9, 7, 6, 4, 6 이다. 일렬로 세워진 막대기를 오른쪽에서 보면 보이는 막대기가 있고 보이지 않는 막대기가 있다. 즉, 지금 보이는 막대기보다 뒤에 있고 높이가 높은 것이 보이게 된다. 예를 들어, 그림과 같은 경우엔 3개(6번, 3번, 2번)의 막대기가 보인다.
N개의 막대기에 대한 높이 정보가 주어질 때, 오른쪽에서 보아서 몇 개가 보이는지를 알아내는 프로그램을 작성하려고 한다.
입력
첫 번째 줄에는 막대기의 개수를 나타내는 정수 N (2 ≤ N ≤ 100,000)이 주어지고 이어지는 N줄 각각에는 막대기의 높이를 나타내는 정수 h(1 ≤ h ≤ 100,000)가 주어진다.
이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 ‘좋은 단어’나 세보기로 마음 먹었다.
평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 ‘좋은 단어’이다. 평석이가 ‘좋은 단어’ 개수를 세는 것을 도와주자.
입력
첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)
다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.
![[백준] 12034번 김인천씨의 식료품가게 (Large)](/images/posts/thumb/baekjoon.png)