코딩 테스트/99클럽 TIL
[백준] 31860 - 열심히 일하는 중
솝제로
2025. 2. 22. 10:54
문제
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)
출력
- 첫째 줄에 송이가 일을 다 하기 위해 걸리는 날의 수를 출력한다.
- 둘째 줄부터 일을 끝내는 날까지 일별로 느낀 만족감을 한 줄씩 구분해 출력한다.
문제 풀이 방법
- N, M, K를 각각 변수에 저장한다.
- for문을 N번 돌면서 해야하는 일의 중요도 정수를 int타입으로 변환해 리스트에 넣는다.
- 리스트를 heap으로 변환한다.
- while문을 돌면서 max값이 K이하가 될 때까지 리스트를 정렬하고 가장 앞의 일을 처리하는 것을 반복한다.
- satisfaction 리스트에 매일 만족감을 계산하여 저장한다.
- day+=1하면서 걸리는 날을 센다.
- day를 출력한다.
- 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]