1202

편집 시간: 2022년 3월 30일 오후 10:05

코드

Algorithm/1202.py at main · Junroot/Algorithm

풀이

담을 수 있는 무게가 작은 가방부터 담으면서, 가방이 담을 수 있는 보석 중에 가장 가치가 높은 보석을 담으면 된다는 것을 알 수 있었다. 다음 가방으로 넘어가면서 앞에서 사용한 보석을 빼고 그 중 가치가 가장 높은 보석을 찾는 방식으로 구현하면 됐다.

이 과정에서 가장 높은 가치를 계속 찾아야되기 때문에 우선순위 큐를 사용했다.

다른 사람 풀이

보석의 정렬을 더 빠르게 하는 방법이 있었다. 카운팅 정렬을 응용한 방식으로 보였다.

mass = [[] for _ in range(max_mass+1)]

for _ in range(N):
    M, V = map(int, sys.stdin.readline().split())
    mass[M].append(V)