[백준] 17612번 쇼핑몰 파이썬

문제링크: https://www.acmicpc.net/problem/17612

소스코드

import sys
input = sys.stdin.readline
import heapq

n,m = map(int, input().split())
# n명, 계산대 m개

cus = [] # 고객번호 배열
item = [] # 물건 갯수 배열

for _ in range(n):
    a, b = map(int,input().split())
    cus.append(a)
    item.append(b)

fin = [] # 계산마친 사람 배열
h = [] # 우선순위 큐
accumulate = [0] * m # 계산대 별 누적시간

for i in range(m):
    heapq.heappush(h, (0, i)) # 초기에는 세 계산대 다 사용해야하므로 (누적시간, 계산대 번호) 를 힙에 넣는다.

for i in range(n):
    ac, num = heapq.heappop(h)
    accumulate[num] += item[i] # 계산시간 만큼 계산대 별 누적시간에 더한다.
    heapq.heappush(h, (accumulate[num], num)) # 추가된 시간을 다시 힙에 넣는다.
    fin.append((accumulate[num], num, i)) # 누적시간, 계산대번호, 인덱스를 배열에 담는다.

fin.sort(key=lambda x: (x[0], -x[1])) # 배열을 내림차순의 누적시간과, 오름차순의 계산대 번호로 정렬 => 누적시간이 같은경우 높은계산대가 먼저 나감

ans = 0

for idx, info in enumerate(fin):
    ans += (idx+1) * cus[info[2]]

print(ans)