문제
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.
| 문제 번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 데드라인 | 1 | 1 | 3 | 3 | 2 | 2 | 6 |
| 컵라면 수 | 6 | 7 | 2 | 1 | 4 | 5 | 1 |
위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.
문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.
문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 보다 작거나 같은 자연수이다.
문제 풀이
데드라인이 어떤 의미인지 파악하는데 오래 걸렸다.
정리하자면 각 문제를 푸는데 1시간이 걸리고, 각 문제의 데드라인에 해당하는 시간이 초과하면 해당 문제는 풀 수가 없다.
즉, 현재시간 time = 1로 초기화 시키고, 위 예시에서 1번을 풀었다 치자. 그러면 한 문제를 풀었으니 시간은 이 될것이고, 현재 시간 time = 2가 된다. 그러면 2번 문제의 데드라인은 1이기 때문에 현재 시간인 2보다 작아서 풀 수 없다.
그렇기 때문에 데드라인순으로 오름차순이 필요하고, 같은 데드라인 이면 많은 컵라면을 주는 문제를 푸는게 이득이므로 두 번째 우선순위로 컵라면에 대한 내림차순을 진행했다.
이후 우선순위 큐를 사용하여 가장 작은 데드라인에서부터 가장 많은 컵라면을 줄때를 구하여 더했다.
import sys
import heapq
input = sys.stdin.readline
n = int(input())
heap = []
for _ in range(n):
deadline, cup = map(int, input().split())
heapq.heappush(heap, (deadline, -cup))
tmp = 0
answer = 0
while heap:
a, b = heapq.heappop(heap)
if tmp < a:
answer += -b
tmp = a
print(answer)결과는 틀렸다.
반례를 알아보니 아래의 두 경우에 틀리고 있었다.
# 데드라인이 남았는데 카운트 안한 경우
3
3 9
3 4
1 1
내 답 : 10, 정답 : 14# 데드라인이 긴 경우가 더 많은 라면을 얻을 수 있는 경우
3
1 25
2 50
2 100
내답 : 125 정담 : 150이러한 반례를 생각하며 코드를 수정하여 통과할 수 있었다.
1 # BOJ 1781 골드2
2 import sys
3 import heapq
4
5 input = sys.stdin.readline
6 n = int(input())
7 heap = []
8 for _ in range(n):
9 deadline, cup = map(int, input().split())
10 heapq.heappush(heap, (deadline, -cup))
11
12 answer = 0
13 time = 1 # 현 시간
14 temp_heap = []
15 while heap:
16 deadline, cup = heapq.heappop(heap)
17 answer -= cup # 우선 데드라인 안쪽이니 더해줌
18 heapq.heappush(temp_heap, -cup) # 더한 값들을 다 저장해줌
19
20 while heap and time == heap[0][0]: # 현재 시간과 같은 데드라인을 가지고 있는 문제들을 발견하면 다 빼내야함
21 possible = heapq.heappop(heap) # 여기서 데드라인이 긴 경우가 더 많은 라면을 얻을 수 있는 경우를 찾아냄
22 if -possible[1] > temp_heap[0]: # 데드라인이 긴 경우가 라면 획득량 > 획득했던 라면량중에 가장 적은 획득량
23 answer -= heapq.heappop(temp_heap) # 가장 적은 획득량을 빼고
24 answer -= possible[1] # 지금 라면 획득량을 더해줌
25 heapq.heappush(temp_heap, -possible[1]) # 이건 다시 이때까지 획득했던 라면량으로 넣어줌
26 time += 1 # 시간 +1
27
28 if answer > 2**31:
29 print(2**31)
30 else:
31 print(answer)우선 입력을 받아 정렬하는 것 까지는 똑같다.
이후 반복문을 통해서 heap의 모든 원소를 조사한다.
line16 ~ 17에서 가장 적은 데드라인의 가장 큰 컵라면 개수를 일단 더해준다. 이때 현재 시간에 따라 데드라인과 비교를 해야할텐데 이 부분은 빠져있다. 왜냐하면 이 부분은 뒷 부분의 코드에 의해서 생각을 안해도 되기 때문. 그리고 이를 통해 반례1 (데드라인이 남았는데 카운트 안한 경우)을 해결할 수 있었다.
line 18에서는 또 하나의 최소힙을 선언하여 더한 컵라면 개수를 저장해준다. 이 부분은 반례2와 같이 더 긴 데드라인의 컵라면 수가 많은 경우를 고려하기 위함이다.
이후 또 한번의 while문을 사용 현재 시간과 같은 데드라인을 가지고 있는 문제들을 모조리 조사한다. 이 부분 덕분에 line 17에서 우선적으로 컵라면 수를 더한것이다.
왜냐하면 두 번째 while문에서 현재 시간과 같은 데드라인은 모조리 조사하여 빼기 때문에 남은 데드라인은 현재 시간보다 클 수 밖에 없기 때문.
즉, 만약 남은 문제중 데드라인이 가장 작은 문제가 현재 시간과 같다면(line 20) heappop을 이용하여 해당 문제를 모두 빼고(line 21) 조사한다.
이후 방금 뺀 문제의 컵라면 수와, 우리가 line 18에서 저장했던 현재까지 더한 컵라면 수의 최소값과 비교를 한다. line 22
이 비교는 반례 2를 해결하기 위함이다.
문제를 푸는 시간은 모든 문제가 1시간으로 똑같은 상황에서 데드라인이 작은 문제의 컵라면 수(temp_heap[0]) < 데드라인이 큰 문제의 컵라면 수(-possible[1]) 라면, 당연히 후자를 선택하는게 더 좋은 선택이지 않은가?
이를 line 22 ~ 25를 통해 해결하였다.
