백준 12865 평범한 배낭 해설/코드 (파이썬) 다이나믹 프로그래밍!

문제 해결 코드만 궁금한 분은 깃허브링크 눌러주세요. 풀이가 2개니까 잘 보고 둘 다 실행 해보세요~

GitHub - Rhyankwon/algorithms

 

문제 설명

다이나믹 프로그래밍이란걸 배운다면 가장 처음 배우게되는 배낭 문제. 나도 사실 이 문제는 파이썬 알고리즘 인터뷰에서 봣던 문제라 크게 어렵지 않게 풀었다.

 

문제 해설이 총 2개인데, 나는 파이썬 알고리즘 인터뷰에서 나온 방식대로 우선 한번 풀어봤다.

 

문제 해결 논리 1

 

1. N개의 행, K+1개의 열로 구성된 행렬을 하나 만든다.

2. 1행은 첫번째 물건만 넣었을 때를 의미하고, k째 열은 배낭이 k무게까지만 수용 가능한 상황을 의미한다.

3. 따라서, 만약 첫번째 물건이 (무게 =4kg, 가치 = 30 )이고 배낭이 7kg까지 수용할 수 있다면 첫째 행의 3번째 열 까지는 0을 입력하고 4번째부터는 첫번째 물건의 가치인 30이 된다.

4. n행은 첫번째 물건부터 n째 물건까지 넣었을 때를 의미한다. 따라서 n째 행의 k째 열의 값은,

[{n-1째 물건까지만 넣은 행의 (k-n)열의 값}에 {n째 물건의 가치를 더한 값}]과,

[n-1째 물건까지만 넣은 행의 k열의 값] 중 더 큰값이다.

 

다시말해서 n행의 k열의 값은, 배낭이 K무게까지 수용 가능일때, 그보다 1kg씩 작은 만큼 수용 가능한 경우마다 n째 물건을 넣을 때와 안 넣을 때를 비교해서 어느 때 더 큰 가치를 가지는지 최대값을 확인해서 넣는다고 생각하면 된다.

이렇게 하면 해당 행렬의 마지막 행, 마지막 열의 값은 우리가 원하는 답을 갖게된다.

 

이게 파이썬 알고리즘 인터뷰 책에서 나왔던 풀이이고 나는 그 기억을 살려서 거의 그대로 풀었는데 6000ms정도가 나왔다. 아무래도 N*K짜리 행렬을 전부 채우니까 필요없는 경우도 많이 계산을 한 것 같다.

 

문제 해결 논리 2는, 다른사람들 풀이를 참고해서 푼건데, 지금 이미 나온 무게와 값의 경우에 대해서만 매번 새로운 물건의 무게를 추가해보고 그게 K값 이하면 값을 추가하고 만약 이미 있는 무게에서, 원래 계산했던 값보다 새로 계산한 값이 더 크면 업데이트를 하고 이런 방식이다. 이렇게 하면 1/3정도로 시간을 줄일 수 있었다.

 

문제 해결 논리 1을 충분히 이해했다면 두번째 논리도 간단히 이해할 수 있을거라고 생각한다. 더 직관적인 풀이긴 한데 사실 내 개인적인 생각으로는 다이나믹프로그래밍의 정석은 논리1이다. 모든 경우에 대한 표를 만들어놓고 가능한걸 다 해보는것이랄까? 근데 두번째가 더 효율적인 풀이이긴 해서, 이제 나도 조금 고급?ㅋㅋ dp를 해보려고 노력해봐야겠다.