백준 12865 힌트

글을 쓰는 이유

처음에는 정렬을 한 다음 동적계획법을 써야하나 싶었다. 그래서 무게별로 정렬을 해보기도 하고 무게대비 가치를 따져보기도 했다.
하지만 어떤 경우에도 반례가 생긴다는 것을 알아냈다.
한참 고민하다가 검색을 해봤더니 머리를 탁 치게 됐다.
좋은 접근 방법인 것 같아서 기록해 놔야겠다.
다시 푸는데 기억이 안나는 경우를 위해 코드를 적지는 않고 힌트만 살짝 적어 놓도록 하겠다.

주요 개념

주요 개념은 {N(물건 수) * K(최대 무게)}개의 배열을 선언하는 것이다.

N번 배열을 순회하며 물건을 하나씩 넣는다고 생각하면 되고
       거기서 K번 배열을 순회하며 어떤 물건을 넣을지 판단한다고 생각하면 된다.