[백준 17612] 2019 정올 1차 고등부 "쇼핑몰"

문제 출처 : https://www.acmicpc.net/problem/17612

17612번: 쇼핑몰

이 문제는 2019년 정보 올림피아드 1차 고등부 1번 문제 입니다.

문제 이해하기

이 문제는 어렵지는 않지만 복잡한 문제 입니다. 쇼핑몰에 들어가는 순서 따로, 그 고객의 id를 알아야 하고 고객이 사는 물건의 개수만큼 시간을 계산하여 계산대에 넣어주어야 합니다. 예제 입력을 가지고 생각해 보겠습니다. 예제에는 10명의 고객이 있고 계산대는 총 3개 입니다. 먼저 처음 계산대에 도착한 3명은 계산대에서 계산을 시작 합니다.

물건 4개를 가진 123번의 계산이 가장 먼저 끝납니다. 4분에 123번이 빠져나가고 다음 순서인 56번이 들어오게 됩니다.

56번과 21번은 5분이 되었을 때 같이 빠져나가게 됩니다. 이 때 계산대 번호가 높은 21번이 먼저 나가게 되고 다음으로 56번이 빠져나갑니다.

새로 2명을 받을 수 있습니다. 45번과 723번이 들어오게 되고 번호가 작은 45번이 앞의 계산대에 가게 됩니다.

5개의 물건을 가진 723번이 빠져 나갑니다. 다음으로 물건 7개를 가진 45번이 빠져 나갑니다.

드디어 14분을 소요하여 3번 계산대에 있는 사람이 빠져나갈 수 있습니다.

이번에도 1번, 2번 계산대가 17분에 같이 나오게 됩니다. 계산대 순서가 높은 55번이 먼저 나가고 13번이 빠져나가게 됩니다.

마지막 순서까지 끝났기 때문에 이제 2번 계산대는 비어 있습니다. 현재 계산하고 있는 73번과 910번중 73번이 먼저 계산이 끝나고 마지막에 910번이 계산 합니다.

이게 마지막으로 계산해 주면 됩니다. 각각의 순서와 id를 곱해준 뒤 더해주어야 합니다. 즉 아래의 식을 계산 합니다.

• 1 * 123 + 2 * 21 + 3 * 56 + 4 * 723 + 5 * 45 + 6 * 34 + 7 * 55 + 8 * 13 + 9 * 73 + 10 * 910

위 식을 계산하면 13900이 나오고 이 값은 답과 일치합니다.

코드 작성하기

그럼 코드를 작성해 보겠습니다.

입력받기

mii = lambda : map(int, input().split())

N, k = mii()

customer = []
for _ in range(N):
    idi, wi = mii()
    customer.append((idi, wi))

고객의 수 N과 계산대의 수 K를 입력 받습니다. 다음으로 N명의 고객 정보를 받습니다. customer라는 리스트를 만들어 각각 고객의 회원번호 idi와 물건의 수 w를 입력 받습니다.

계산대 초기화

from heapq import heappush, heappop
for i in range(k):
    heappush(counter, (0, i))

처음에는 계단대 모두가 비어 있기 때문에 차례대로 빈 계산대로 입장 합니다. 이 때 계산대 counter는 우선순위큐를 사용해 줍니다. 계산대가 비어 있기 때문에 시간은 0이고, 입장한 순서대로 0부터 K-1까지 우선순위 큐에 들어가게 됩니다.

계산대 들어가기

finished = []
time_check = [0] * k

for i in range(N):
    time, idx = heappop(counter)
    time_check[idx] += customer[i][1]
    heappush(counter, (time_check[idx], idx))
    finished.append((time_check[idx], -idx, i))

앞서 초기화는 계산대에 사람이 들어가 있기는 하지만 계산이 전혀 안되어 있습니다. 즉 언제 계산대에 빠져나오는지 계산이 전혀 안되어 있습니다. 이제 각 계산대에 언제 사람이 나올지 계산해 보겠습니다.

counter의 idx는 몇번째 계산대인지를 나타냅니다. 각 계산대에 사람들이 얼마나 머물지를 누적하여 더해줍니다. 얼마나 머물지는 각 고객의 물건의 개수만큼 입니다. 비어있는 계산대가 나타나면 i번째 사람이 들어가고 idx번째 계산대인 time_check에 얼마나 머물지를 더해줍니다.

마지막으로 finished는 계산이 완료된 사람들이 들어갑니다. 그냥 finished에 들어가는 것이 아니라 먼저 이 사람이 몇분에 계산이 끝났는지를 알아야 합니다. 그것이 time_check[idx]값 입니다. 여기에 계산을 마친 고객의 시간이 동일하다면 계산대 번호가 높은 사람이 먼저 나와야 합니다. 시간은 오름차순, 계산대 번호는 내림차순으로 정렬해야 하기 때문에 계산대 번호 앞에 - 기호를 붙여주었습니다. finished 리스트를 정렬 했을 때 오름차순으로 정렬할 것이기 때문에 계산대 번호에 -1을 곱해주어야 내림차순 정렬이 됩니다. 마지막으로 계산을 끝낸 고객의 순서를 넣어줍니다.

결과 출력하기

rst = sum(customer[finish[2]][0] * (i + 1) for i, finish in enumerate(sorted(finished)))
print(rst)

쇼핑몰을 나가는 순서를 출력하는 것이 아니라 나가는 순서를 곱해준 뒤 모두 더해주어야 합니다. 첫 번째로 쇼핑몰을 빠져나가는 손님에게는 1을 곱하고, 2번째로 나가는 손임에게는 2를 곱하는 식 입니다. 최종적으로 마지막 손님은 N을 곱해준 뒤 모두 더한 값을 출력해 주어야 합니다.

finished는 오름차순으로 정렬되어 있습니다. finished[0]에는 쇼핑몰을 빠져나간 시간, finished[1]에는 계산대 번호에 -1이 곱해진 값이 들어가 있습니다. 이렇게 하여 쇼핑몰 시간에는 오름차순, 계산대 번호에는 내림차순이 됩니다. 마지막으로 finished[2]에는 고객이 입장한 순서가 들어가 있습니다.

고객의 id를 알기 위해서 입장한 순서를 알아야 합니다. 그것이 finished[2] 입니다. 그리고 고객 정보는 id와 물건의 개수가 있기 때문에 최종적인 고객의 id 값은 customer[finished[2]][0]으로 알 수 있습니다. 여기에 i + 1값을 곱해 모두 더해주면 원하는 결과를 얻을 수 있습니다.

코드를 압축시켜 놓아 이해가 어려울 수 있습니다. 정렬부터 하나하나 풀어서 작성하면 이해가 쉽습니다. 아래 풀어서 작성된 코드 입니다.

finished.sort()
total = 0
cnt = 1
for time, idx, i in finished:
    total += customer[i][0] * cnt 
    cnt += 1

print(total)

전체 코드

전체 코드를 확인해 보겠습니다.

from heapq import heappush, heappop
mii = lambda : map(int, input().split())

N, k = mii()

customer = []
for _ in range(N):
    idi, wi = mii()
    customer.append((idi, wi))

counter = []

for i in range(k):
    heappush(counter, (0, i))

finished = []
time_check = [0] * k

for i in range(N):
    time, idx = heappop(counter)
    time_check[idx] += customer[i][1]
    heappush(counter, (time_check[idx], idx))
    finished.append((time_check[idx], -idx, i))

rst = sum(customer[finish[2]][0] * (i + 1) for i, finish in enumerate(sorted(finished)))
print(rst)