오구의코딩모험

문제 3줄 요약 1. 상덕이는 도둑이다. 2. 보석은 총 N개, 무게는 M, 가격은 V 3. 상덕이 가방 개수 K개, 담을 수 있는 무게는 C이며 가방 당 최대 한 개, 최대 얼마까지 훔칠 수 있을까? 문제를 읽고 직관적으로 느낀 해결법은 가방에 담을 수 있는 최대 무게가 작은 가방부터 무게 당 가격이 높은 보석을 넣어야한다는 것이었다. 따라서 무게 당 가격이 높은 보석 순으로 정렬하고 차례대로 가방에 넣고 해당 보석은 제외시키는 방법을 하니 바로 시간 초과 ㅎ.. 아무래도 리스트에서 값을 지우는 것은 리스트를 한바퀴 돌아야하므로 효율적이지 못했던 것 같다. 그리고 한번 거쳤던 보석들도 다시 재비교 한다는 것을 알 수 있었다. Ex) 무게가 1, 2, 3 가격이 5,6,7인 보석이 있다. 가방이 1,2,..