[파이썬] 백준 17612 : 쇼핑몰 (골드2)

[파이썬] 백준 17612 : 쇼핑몰 (골드2)

• https://www.acmicpc.net/problem/17612
  

---

풀이

방향성 생각

• K개의 계산대 중 최소 정보를 계속 찾아야 함 -> 힙 사용
• 같은 시간대에서 여러 명이 빠질 수 있는 케이스 생각하기

---

전체코드

from collections import deque
import heapq as hq
import sys

input = lambda : sys.stdin.readline().rstrip()

N,M = map(int,input().split())

Q = deque()
for _ in range(N):
    Q.append(list(map(int,input().split())))

# 사람들 계산대에 보내기
heap = []
for line in range(min(N,M)):
    x,t = Q.popleft()
    hq.heappush(heap,(t,-line,x))

done = []
while Q:
    t,line,x = hq.heappop(heap) # 힙에서 가장 빨리 끝나고, 가장 출구에 가까운 사람 뽑는다.
    done.append(x) # -> 출구로 보내기
    empty = deque([line]) # 비어있는 라인 저장

    # 같은 시간에 여러 계산대에서 계산 종료 가능
    while heap:
        nt,nline,nx = hq.heappop(heap)
        if t == nt: # 같은 시간에 종료됐으면 힙에서 더 뽑기
            done.append(nx)
            empty.append(nline)
        else: # 그렇지 않으면 다시 힙에 넣기
            hq.heappush(heap,(nt,nline,nx))
            break

    # 비어있는 계산대 채우기
    while empty:
        line = empty.pop() # 비어있는 계산대에
        if Q: # 사람 추가
            nx,nt = Q.popleft()
            hq.heappush(heap,(t+nt,line,nx))
        else:
            hq.heappush(heap,(0,line,0))

# 잔여 정보 처리하기
while heap:
    _,_,x = hq.heappop(heap)
    done.append(x)

answer,cnt = 0,1
for val in done:
    if val:
        answer += cnt*val
        cnt += 1
print(answer)

코멘트

• 동시간대에 같이 나가는 케이스만 체크해주면 금방 풀 수 있다.