1781번: 컵라면
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라
www.acmicpc.net
import heapq
import sys
if __name__ == '__main__':
heap = []
N = int(sys.stdin.readline().rstrip())
for _ in range(N):
deadline, ramen = map(int, sys.stdin.readline().split())
heapq.heappush(heap, [-ramen, deadline])
ans = 0
flag = [0] * (N + 1)
while heap:
ramen, deadline = heapq.heappop(heap)
for i in range(deadline, 0, -1):
if flag[i] == 0:
flag[i] += 1
ans -= ramen
break
print(ans)
# 9
# 5 5
# 4 6
# 4 12
# 3 8
# 4 18
# 2 10
# 2 5
# 1 7
# 1 14
골드 I 등급 문제인데 아무것도 보지 않고 꽤 쉽게 풀었다.
며칠전에 이것과 거의 비슷한 유형의 문제를 풀었기도 하고 문제유형에 우선순위 큐 라고 나와있는걸 봤기 때문이다.
비슷한 유형의 문제: www.acmicpc.net/problem/13904
13904번: 과제
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.
www.acmicpc.net
우선 이 문제는 제한 기간내에 가장 많은 컵라면을 획득해야하므로,
컵라면의 수를 기준으로 max 우선순위 큐 에 담아줘야한다.
그 다음, 중요한것은 각 날짜에 문제를 풀었는지에 대해 기록하는 날짜 배열을 생성하여 기록해놓은것이다.
우선순위 큐에서 최대 컵라면을 꺼내면서 해당 컵라면의 데드라인에 해당하는 일차에 이미 획득한 컵라면이 있는지 확인하고 없다면 해당 컵라면을 획득하고 (결과값에 누적시키고), 해당일차에 컵라면을 획득했다는것을 기록해준후, 날짜 loop를 빠져나온다.
이 컵라면은 최대로 획득 가능한 컵라면이기 때문에 획득할 수만 있다면 나중은 고려할 필요없이 무조건 최선의 결과를 낳는다. 이게 바로 그리디 알고리즘의 핵심인 것이다.
만약 해당하는 일차에 획득한 컵라면이 있다면 (flag 배열의 해당일차에 해당하는 인덱스 값이 1이라면) 하루씩 감소시키면서 획득할 수 있는 날이 있다면 해당 일차에 획득하도록 한다.
이 과정을 반복하면 최대 컵라면을 획득할 수 있다.
그리고 효율을 좀 더 올려야할듯하다.
heap 에 있는 모든 요소가 없어질때까지 반복할 필요없이,
데드라인의 최대일차 만큼 컵라면을 획득했다면 heap 에 남은 요소들은 더이상 순회할 필요가 없어진다.