반응형 그리디16 백준 1202번 보석 도둑 - C++(cpp) 풀이 + 그림 설명 1. 용량이 적은 가방부터 채운다. 2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다. 3. 남은 가방에 대해 1-2를 반복한다. 1. 용량이 작은 가방부터 채운다. 한 가방에는 한 개의 보석만 담을 수 있으므로 그리디 하게 풀 수 있는 상황이다. 용량이 적은 가방에 들어가지 못한 보석이 용량이 큰 가방에는 들어갈 수도 있다. 반대로 용량이 큰 가방에 들어가지 못한 보석이 용량이 적은 가방에는 들어갈 일은 없다. 따라서 용량이 작은 가방부터 최선으로 채워나가면 최선의 결과를 얻을 수 있음이 보장된다. 2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다. 먼저 용량이 C인 가방에 담을 수 있는 보석들을 걸러내기 위해 보석을 무게 순으로 정렬한다. 아래와 같은 상황이고, 가방의.. 2022. 1. 28. 이전 1 2 3 4 다음 반응형
