boj 1781(컵라면)

틀린 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = []
for _ in range(N):
    arr.append(tuple(int (x) for x in input().split()))
arr.sort(key=lambda x: (x[0],-x[1]))
sol = 0 
a, b = arr[0][0],arr[0][1]
sol+= arr[0][1]
for i in range(1,len(arr)):
    if(arr[i][0]>a):
        a = arr[i][0]
        sol+=arr[i][1]
print(sol)

반례:

9

5 5

4 6

4 12

3 8

4 18

2 10

2 5

1 7

1 14

-사고 과정-

위의 반례를 예시로 들면 저걸 내림차순으로 정렬을 합니다.

(5 , 5) → (4, 18) → (4, 12) → (4, 6)… 이런 식으로 말입니다.

틀린 이유는 제가 3번째 칸에 (3, 8)이 아닌 (4, 12)가 들어갈 수 있다는 생각을 못했습니다.

import sys
input = sys.stdin.readline

N = int(input())
arr = []
for _ in range(N):
    arr.append(tuple(int (x) for x in input().split()))
arr.sort(key=lambda x: (-x[0],-x[1]))
sol = 0 
a, b = arr[0][0],arr[0][1]
arr1 = [0]*(a+1)
m = a
arr1[m] = b
max=0
ans = 1
for i in range(arr[0][0]-1,0,-1):
    max=0
    for j in range(ans, len(arr)): 
        if(arr[j][0]>=i):
            if(arr[j][1]>max):
                max=arr[j][1]
                arr1[i]=max
                ans= j+1
        else:
            break

print(sum(arr1)-arr1[0],end="")

-반례-

못 찾았습니다… 다른 반례들 찾아서 계속해봤는데 다 정답이 나오는데 어디서 반례가 생긴 건지 잘 모르겠습니다…

-사고방식-

일단 처음엔 가장 데드라인이 큰 수 중 가장 많은 컵라면 수가 들어갈 것입니다.

첫 번째 반복문은 일차를 의미합니다.

가장 큰 데드라인 일 수부터 1일 차까지 줄여가면서 채워나갔습니다.

위 반례를 다시 사용하면 데드라인은 5가 가장 크므로 deadline 5부터 4 3 2 1 이렇게 채워나가는 것입니다.

두 번째 반복문이 이제 어떤 값이 들어갈지 정해주는 반복문입니다.

ans 변수가 뭐냐면 이제 (5, 5)와 (4, 18)은 사용하였으니 (4, 12)부터 탐색을 시작해야겠죠? 그런 의미입니다.

변수명을 깊게 생각해보지 못해서 이렇게 되었습니다..

근데 아마 이렇게 풀었어도 시간초과가 분명히 떴을 거긴 합니다..

아무튼 반례 찾아주시면 꼭 댓글 적어주세요..

---

코드

import sys
import heapq

input = sys.stdin.readline
N = int(input())
problems = [list(map(int, input().split())) for _ in range(N)]
problems.sort()

solved_problems = [] # 해결한 문제를 저장하는 우선순위 큐

for problem in problems:
    heapq.heappush(solved_problems, problem[1])

    while problem[0] < len(solved_problems):
        heapq.heappop(solved_problems)

print(sum(solved_problems))

위 문제는 우선순위 큐를 사용하였습니다.

---

후기 및 풀이

아직 우선순위 큐를 잘 사용하지 못한다는 걸 느꼈습니다.

그리고 우선순위 큐라고 돼있는데 굳이 이상하게 풀면 안 된단 것도요…

제가 위에서 푼 방식을 은 다 내림차순으로 하여서 끝에서부터 채우는 느낌이었는데 해답법은 반대였습니다.

 

처음에 오름차순으로 정리를 해줍니다.

위에 반례를 사용하면

(1, 7) → (1, 14) → (2, 5) → (2, 10) → (3, 8) → (4, 6) → (4, 12) → (4, 18) → (5, 5)

이렇게 오름차순 정리가 될 것입니다.

 

이제 이 코드들이 반복문에 들어가는데 problem [0]은 데드라인을 의미, problem [1]은 컵라면 수를 의미합니다.

처음엔 7이 들어가고 그다음은 [1 ,14]가 되지만 그렇게 되면 반복문의 조건에 어긋나고 heappop에 의해 1이 사라지게 됩니다.

 

이런 식으로 [14] → [14 ,5] → [14,5,10] → [14, 10] → [14,10,8] → [14,10,8,6] → [14,10,8,6,12] → [14,10,8,12] → [14,10,8,12,18] → [14,10,12,18] → [5,10,12,14,18] 이 될 겁니다.

그리고 합을 더해주면 답이 됩니다.