[모각코] 210717 Today I Learned

백준 #1202 보석 도둑

 

1202번: 보석 도둑 (acmicpc.net)

1202번: 보석 도둑

 

** 틀린 알고리즘

import sys

N, K = map(int, sys.stdin.readline().split())    # 보석 개수, 가방 개수
jewelry = []    # 보석 정보 저장
bag = []    # 가방 최대 무게 저장
for i in range(N):
    m, v = map(int, sys.stdin.readline().split())    # m: 보석 무게, v: 보석 가격
    jewelry.append((m, v))
for i in range(K):
    bag.append(int(input()))

jewelry.sort(key=lambda x: x[1])    # 보석 가격을 기준으로 오름차순 정렬
bag.sort()

max_value = 0   # 훔칠 수 있는 보석 가격 합의 최대값

for i in range(N-1, -1, -1):    # 보석 가격 큰 것부터
    if jewelry[i][0] <= bag[0]:
        max_value += jewelry[i][1]
        bag.pop(0)
    if len(bag) == 0:
        break

print(max_value)

 

 

 

보석 정보들을 보석 가격을 기준으로 오름차순 정렬하고, 가방 무게를 오름차순으로 정렬해서 가방 무게가 적은 것부터 가격이 큰 보석을 선택해나가는 알고리즘을 생각했다. 결론부터 말하면 틀린 알고리즘이다. ㅜ 처음 타임아웃이 떠서 input을 sys로만 고치면 될 거라고 생각했는데 갑자기 틀렸습니다 가 나와서 당황했다. 알고리즘을 다시 생각해보니 내가 틀린 게 맞았다. 무게가 적은 가방부터 보석을 선택해 나가면서 가방 무게보다 많이 나가서 담지 못 한 보석은 다음 가방이 보석을 선택할 때도 고려하지 않아도 된다고 생각했는데, 고려를 하는 게 맞다.

 

이중 for문만 쓸 수 있으면 뚝딱 만들어지는데 당연히 타임아웃이 난다 ... 무엇을 기준으로 정렬해야 할까 ㅜ for문 하나로 뚝딱 써지길래 웬일인가 했더니 역시나 한 번에 맞을 리 없음 ㅜ