최근에 백준에서 다이나믹 프로그래밍(DP)를 공부하다가 처음 보는 유형의 문제가 있어 글을 쓰게 되었습니다. [ 관련 문제 : 백준 12865 평범한 배낭 www.acmicpc.net/problem/12865 ] Knapsack 문제란? 어떤 도둑이 보석상에 들어가 보석을 훔친다고 했을 때, 배낭의 용량을 넘치지 않게 담아야 하고, ( 넘치면 훔칠 수 없다는 가정 ) 돈을 가장 많이 벌 수 있도록 담는 방법에 대해 얘기하는 것을 Knapsack 문제라고 합니다. Knapsack 문제의 경우는 담는 물건이 나눌 수 있는 경우, 단순하게 담을 수 있냐 없냐 (0-1) 두 가지의 종류가 있지만 지금은 단순하게 담는 0-1 Knapsack 문제에 대해 쓰겠습니다. 이게 DP랑 무슨 상관?? 단순하게 생각해보면 ..