이번 문제는 동적 프로그래밍을 이용하여 배낭에 넣을 수 있는 최대 가치 값을 찾아내는 문제이다. 골드 난이도 답게 난도가 좀 있었는데 혼자서 이리저리 짜보다가 생각처럼 잘 되지 않아 ChatGpt의 도움을 약간 받아 해결하였다. 그러면 어떻게 문제를 풀었고 어디가 문제였는지 살펴보자. 무엇이 반복되는가? 이전 글에서도 서술 했지만 동적 계획법의 핵심은 반복되는 요소를 기록하여 시간을 단축시키는 것이다. 그러면 무엇이 반복되는 것이고 그것을 어떤 방법으로 기록할 것인지가 핵심이 되겠다. 문제는 배낭의 넣을 수 있는 물건들의 최대 가치값만을 요구하고 있기 때문에 안에 몇개가 들어가는지, 몇종류가 들어가는지는 중요하지 않다. 즉, 배낭에 무게별로 들어가는 가치합이 반복되는 요소가 될 것이다. 그럼 남은 문제는..
