이번 문제는 백준의 골드 5 문제인 평범한 배낭 문제이다.
배낭 문제는 이미 유명한 문제로, Knapsack 문제로도 불린다.
유명한 만큼 다양한 풀이 방법이 이미 공개가 되어 있는데,
차근차근 한 번 직접 생각해보자.
문제의 제약 조건은 우선 최대 100개의 물건이 입력으로 들어오는데,
여기서 사실 물건의 개수 이외의 조건은 생각하지 않아도 될 것 같다.
다른 조건들은 문제를 푸는 시간에 영향을 끼치지 않을 것 같다.
이제 어떤 방식으로 풀 것인지를 생각해보자.
가장 먼저 드는 생각은 백트래킹을 통한 완전탐색이다.
과연 100개의 물건을 완전탐색 하려면 시간복잡도가 얼마나 될까?
간단히 생각해보면, 넣는다, 넣지 않는다 두 가지 선택지가 있다.
아무 가지치기 없이 완전탐색만 한다면, O(2^N)이 걸리게 된다는 말이다.
즉, 2^100 만큼의 시간이 걸린다는 것인데 이 방법은 좋지 않을 것 같다.
뭔가 아이디어를 써서 가지치기를 잘 하면 사용할 수도 있다는 생각은 든다.
DP?
그럼 다른 방법은 어떤 방법이 있을까?
무게를 채워 나가면서, 최대로 가치를 높이는 방법?
아이템 수를 채워, 특정 무게를 맞추었을 때 최대인 가치를 저장하며 진행한다면?
DP와 같은 형태로 매 단계를 항상 최대 가치로 갱신해가며 진행하는 것이다.
2차원 배열의 DP 배열을 선언해서 한 번 시도해보자.
배열의 행을 각 물건으로 잡고, 열을 물건을 담았을 때의 무게라고 생각하자.
각 물건은 해당 물건을 담을 수 있는 무게가 되면, 가치를 배열에 저장하도록 한다.
예컨대, 아래의 표처럼 채울 수 있을 것이다.
주어진 예시에서 첫 물건이 6의 무게를 가졌기 때문에, 6부터 가치를 채울 수 있다.
그럼 그 다음부턴 어떻게 채워 나갈 수 있을까?
목표가 최대 가치를 구하는 것이기 때문에, 무게에 대해 항상 최대를 유지해야 한다.
따라서, 다음 물건부터는 본인의 가치와 이전 물건의 가치를 비교하며 갱신한다.
즉, 우리는 아래의 경우들을 생각하며 갱신을 해야 한다.
- 현재 넣으려는 물건의 무게가 담을 수 있는 무게라면?
이전 물건까지의 가치와현재 물건을 담을 수 있는 시점의 가치 + 현재 물건의 가치를 비교한다.
- 현재 넣으려는 물건의 무게가 담을 수 없는 무게라면?
이전 물건까지의 가치를 그대로 가지고 내려온다.
그 결과 두 번째 물건은 아래와 같이 채워질 것이다.
j가 4가 되는 순간, 물건을 채울 수 있게 되는데 6부터는 비교가 들어간다.
이전 무게인 6에서 최대 가치를 13으로 갱신했으므로, 해당 무게를 들고 내려온다.
세 번째 물건의 갱신은 아래와 같이 이루어진다.
j가 3이 되는 순간, 물건을 채울 수 있게 되는데 4부터는 비교가 들어간다.
이전 물건의 무게인 4에서 최대 가치가 8이었으므로, 해당 무게를 들고 내려온다.
j가 6인 시점 부터는 갱신된 최대 가치가 13이었으므로, 해당 무게를 들고 내려온다.
j가 7이 된 시점이 이 문제를 푸는 핵심 동작이 된다.
현재 물건의 무게가 3이므로, j가 4였던 시점의 무게에 더할 수 있다.
그 말은, 가방에 무게 4짜리 물건만 들어있던 시점에 3을 넣는다는 말과 같다.
즉, 표와 같이 갱신이 되며 문제를 해결할 수 있다.
DP로 풀 수 있다는 사실이 굉장히 유명한 문제였다.
조금 찾아보니 앞서 말했던 백트래킹에 조건을 잘 걸어서 풀 수도 있다고 한다.
또, BFS와 분기 한정법을 같이 사용해서도 풀 수 있다고 한다.
역시 알고리즘 문제는 풀기 나름이고 정답이 없는 것 같다.
생각의 범위를 넓히기 위해 더 많은 공부가 필요할 것 같다.