백준 – 평범한 배낭(12865)

문제

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

풀이

자, 이 문제는 사실 뭐 시간 제한만 없다면, combination을 사용해서 모든 조합을 구한 다음에, 그 조합에 따라서 계산을 해주고 최대값을 찾으면 된다. 하지만 이거는 너무 오래걸린다. 그리고 생각해보면, DP냄새가 난다. 뭔가 이전에 구해놨던거를 활용해서 현재거를 구할 수 있을것 같은 느낌...

배가 아프면 화장실을 가듯, DP냄새가 나면 바로 테이블을 그리자.

다만 배낭문제 같은 경우, 가방이 감당 가능한 무게를 고정하는게 아니라 1씩 증가시킨다는 아이디어는 사실 떠오르기가 어렵다. 그래서 DP테이블도 그리기가 어려운데, 이거는 그냥 외우자. 다음에 비슷한 DP문제가 나왔을때 테이블을 어떻게 그려야 할지에 대한 감을 이렇게 여러 문제를 외우면서 얻을 수 있다 (고 생각한다).

아무튼! DP테이블을 채우는 과정을 소개하겠다.

편하게 설명하기 위해서 우선 앞에 부분은 채워넣었다.

두번째 물건은 무게가 4이기 때문에, 가방이 감당 가능한 무게 3에 넣지 못한다. 그래서 가방이 감당 가능한 무게 3에서 첫번째 까지의 물건을 막 넣었을때, 최대로 얻는 가치를 입력해준다.

가방이 감당 가능한 무게가 4일때는 두번째 물건을 넣을 수 있는데, 이때, 바로 넣는게 아니라 두번째 물건을 안넣은 상태에서 4까지 물건을 막 넣었을때의 최대 가치랑 비교해서 더 큰값을 넣어야 한다. 지금은 바로 넣는게 더 이 득이다.

가방이 감당 가능한 무게가 5일때는, 두번째 물건을 넣었을때의 가치 + 남은 무게에서 가장 최대의 가치 vs 두번째 물건을 안넣었을때의 최대 가치 중 더 큰 값을 넣으면 된다.

가방이 감당 가능한 무게가 6일 때도 마찬가지!

자! 이렇게 쫙쫙쫙쫙 입력한 다음에, 맨 마지막에 있는값이 가방이 감당 가능한 무게가 7일때, 물건들을 자알~넣어서 그 가치가 최대가 되는 값이다.

핵심은 '현재 물건을 넣느냐, 안넣느냐, 어떤게 더 이득인가?' 이 생각이다. 다만 이게 1 ~ 7까지 무게별로 따져봐야겠다는 생각은 잘 안들기 때문에, 이 풀이는 그냥 외우자 😀

코드

https://github.com/airman5573/algorithm-toolkit-in-javascript/blob/main/%EB%B6%84%EB%A5%98/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D/%ED%8F%89%EB%B2%94%ED%95%9C-%EB%B0%B0%EB%82%AD/answer.js

Add Comment