백준 1781번 컵라면 (Python)

N개 문제의 데드라인과 문제를 맞힐 경우 주어지는 컵라면의 개수가 있을 경우 N시간 안에 받을 수 있는 최대 컵라면 개수를 구하는 문제입니다.

 

 

아이디어 1. 컵라면의 개수로 내림차순 정렬

우선 문제를 풀었을 때 받을 수 있는 컵라면의 개수가 많은 것부터 푸는 것이 좋다고 생각했습니다.

그래서 1~N 각 초마다 문제를 풀 경우 해당 초에 얻은 컵라면의 개수를 저장할 수 있는 배열을 선언하고, 데드라인 내에 문제를 풀 수 있다면 해당 초에 컵라면의 개수를 저장하도록 했습니다. 이 후 배열 원소의 총합을 답으로 출력했습니다.

...

# resolvedProblems에 해당 초에 푼 문제의 컵라면 개수를 저장
for deadline, ramen in problems:
    for i in range(deadline, 0, -1):
        if resolvedProblems[i] == 0:
            resolvedProblems[i] = ramen
            break

하지만, N <= 200,000 이므로 만약 모든 문제의 데드라인이 같다면 해당 데드라인부터 1까지 반복문이 계속 실행될 수 있으므로 시간초과가 발생했습니다.

 

이 후, 데드라인 내에 문제를 풀 수 있는 초가 존재하는지 찾는 방법을 반복문 외의 효율적인 방법을 찾아보았지만 생각이 나지 않아 포기하게 되었습니다.

 

 

아이디어 2. 데드라인으로 오름차순 정렬

데드라인으로 오름차순으로 정렬한 뒤, 1초부터 N초까지 이동하면서 해당 초에 얻을 수 있는 최대 햄버거 개수를 가진 문제를 풀도록 했습니다.

해당 초에 얻을 수 있는 햄버거의 개수를 구하는 것은 Priority Queue를 활용했습니다.

각 초에 데드라인이 걸칠 경우 해당 초 안에 문제를 풀 수 있다는 의미이므로 PQ에 넣어줍니다. PQ의 값은 햄버거 개수의 내림차순으로 정렬되도록 했습니다. 

...

# pq 안에 현재 초까지 얻을 수 있는 햄버거 개수가 내림차순으로 정렬되어 있음
j = 0
for i in range(1, N+1):
    while j < N and problems[j][0] <= i:
        pq.put((-problems[j][1], problems[j][0]))
        j += 1

    while not pq.empty():
        temp = pq.get()
        if temp[1] >= i:
            answer += -temp[0]
            break

하지만 위와 같은 경우 만약 (1, 1), (2, 1), (3, 10), (3, 10) 와 같이 문제가 주어질 경우

1초에 1개 2초에 1개 3초에 10개로 12개 밖에 차지하지 못하게 됩니다. (실제 정답은 1초에 1개 2초에 10개 3초에 10개로 21개입니다.)

그러므로 다른 방법을 찾아보게 되었습니다.

 

 

아이디어 3. 데드라인으로 내림차순 정렬

데드라인으로 오름차순이었던 것을 내림차순으로 바꾸어주었습니다.

해당 초에 항상 햄버거를 가장 많이 얻을 수 있는 문제를 풀게 함으로써 최대 햄버거 개수를 구할 수 있도록 했습니다.

from queue import PriorityQueue
import sys
input = sys.stdin.readline

N = int(input())
problems = [list(map(int, input().split())) for _ in range(N)]
answer = 0
pq = PriorityQueue()
problems.sort(key=lambda x: (-x[0], -x[1]))

j = 0
for i in range(N, 0, -1):
    while j < N and problems[j][0] == i:
        pq.put((-problems[j][1], problems[j][0]))
        j += 1

    while not pq.empty():
        temp = pq.get()
        if temp[1] >= i:
            answer += -temp[0]
            break
print(answer)

 

 

다른 풀이

문제의 다른 풀이도 살펴보았을 때 더 효율적인 풀이가 있었습니다.

 

우선, 데드라인으로 오름차순으로 정렬을 합니다.

그 다음, 문제를 풀어 얻은 컵라면 개수를 저장할 정답 배열을 선언해줍니다. 정답 배열은 오름차순 정렬이 되고 최소 힙으로 선언되어 있어 첫 번째 원소가 가장 작은 원소입니다.

1초부터 시작하도록 한 뒤, 데드라인으로 정렬된 문제를 반복문을 돌려줍니다.

만약 현재 문제의 데드라인이 현재 초보다 높을 경우 문제를 풀 수 있으므로 정답 배열에 heappush해줍니다.

현재 문제의 데드라인이 현재 초보다 낮고 정답 배열의 첫 번째 원소보다 현재 문제의 컵라면 개수보다 클 경우 현재 문제를 푸는 것이 더 맣은 컵라면을 얻을 수 있는 방법이므로 첫 번째 원소를 heappop하고 현재 컵라면 개수를 heappush 해줍니다.

 

현재 초보다 데드라인이 높을 경우 우선 정답 배열에 넣어줍니다. 현재 초보다 데드라인이 낮지만, 정답 배열 안에 현재 문제의 컵라면보다 작은 원소가 있다면 해당 원소를 제거하고 현재 문제의 컵라면 개수를 넣어주는 식입니다.

 

 

한 번의 반복문으로 실행이 되기 때문에 훨씬 효과적인 방법이라고 생각되어 다른 풀이도 한 번 작성해보았습니다.

 

 

 

 

 

 

 

그리디 알고리즘 풀이에 아직 많이 익숙하지 않아 조금 더 연습해보아야 할 것 같습니다...