BOJ 12865: 평범한 배낭

https://www.acmicpc.net/problem/12865

코드를 짰는데 중복으로 물건을 고를 수 있게 짜서 이걸 어쩌냐 하다가 그냥 포기하고 다른 분의 풀이를 봤다. 내가 다이나믹 프로그래밍이라고 하면 뭔가 생각이 점화식을 어떻게 짜는지에만 몰두하느라 생각을 우연하게 하지 못한 것이 패착인 것 같다. 나이브한 솔루션인 전체 탐색에 메모이제이션을 이용해서 시간을 줄이는 방식이라고 보면 된다. 나이브한 솔루션은 아이템 i를 뽑냐, 뽑지 않냐로 경우의 수를 나누어서 N번째 (1부터 시작했을 때) 아이템까지 확인하는 방식이다. 정말 간단하지 않은가..?? 좀 더 다양한 DP 문제를 풀면서 생각의 유연성을 길러야 할 것 같다는 반성으로 마무리하겠다.