[백준] 31860 - 열심히 일하는 중

문제
N개의 일에 각각의 중요도를 산정하고 중요도가 높은 일부터 한다.
하루에 하나의 일만 처리할 수 있으며 일을 처리한 후 그 일의 중요도가 M만큼 감소한다.
일의 중요도가 K이하가 되면 그 일은 완료한 것으로 간주한다.
전날의 만족감이 Y, 오늘 할 일의 중요도가 P라고 할 때 오늘의 만족감은 [Y/2]+P이다.

 

 

입력

• 첫째 줄에 N, M, K가 공백으로 구분되어 주어진다.(2>=N<=2,000;1<=M<=5;1<=K<=3)
• 둘째 줄부터 N개의 줄에 걸쳐 해야하는 일의 중요도 정수 Di가 주어진다.(M<Di,K<Di,Di<=1,000)

 

출력

• 첫째 줄에 송이가 일을 다 하기 위해 걸리는 날의 수를 출력한다.
• 둘째 줄부터 일을 끝내는 날까지 일별로 느낀 만족감을 한 줄씩 구분해 출력한다.

 

문제 풀이 방법

1. N, M, K를 각각 변수에 저장한다.
2. for문을 N번 돌면서 해야하는 일의 중요도 정수를 int타입으로 변환해 리스트에 넣는다.
3. 리스트를 heap으로 변환한다.
4. while문을 돌면서 max값이 K이하가 될 때까지 리스트를 정렬하고 가장 앞의 일을 처리하는 것을 반복한다.
5. satisfaction 리스트에 매일 만족감을 계산하여 저장한다.
6. day+=1하면서 걸리는 날을 센다.
7. day를 출력한다.
8. for문을 day만큼 돌면서 satisfaction 리스트를 출력한다.

 

작성한 코드

import sys
import heapq

N, M, K = list(map(int, sys.stdin.readline().strip().split()))
tasks = []
[tasks.append(-int(sys.stdin.readline().strip())) for _ in range(N)]
heapq.heapify(tasks)
    
day = 0
satisfaction = []
top = heapq.heappop(tasks)
satisfaction.append(-top)
heapq.heappush(tasks,top+M)

while -tasks[0]>K:
    top = heapq.heappop(tasks)
    satisfaction.append(satisfaction[day]//2+(-top))
    top+=M
    heapq.heappush(tasks,top)
    day+=1

print(day+1)
[print(satis) for satis in satisfaction]