백준 12865 : 평범한 배낭 - javascript(dp)
문제 출처
https://www.acmicpc.net/problem/12865
정답 풀이
풀이 보니까, dp로는 유명한 문제라는데
아직도 못 푸는 나 자신 머리 한대 때리고 시작하자.
이해하면 코드는 간단하나,
이해하기 생각보다 빡셌다.
다른 분들의 블로그를 봐도 잘 이해가 안갔고, 그래서 내가 이해한 방식대로 글을 작성해볼 예정이다.
## dp 그래프 생성
아래와 같이 2차원 그래프 dp를 생성해줄 것이다.
세로 의미: 각 물건의 무게와 가치
가로 의미: 준서가 버틸 수 있는 무게
그렇다면 dp 그래프의 의미는 어떻게 될까?
각 물건을 넣고, 안넣고에 따라서 + 준서의 배낭 각 무게에 따라의 '가치'를 계속 update 해줄 것임.
(이해가 안가도 아래 쭉 예시를 읽어보자 !)
## 초기화
아래 두가지 경우는 모든 값이 0일 것이다.
- i가 0일 때, 즉 그 어떤 물건도 고려하지 않을 때
- j가 0일 때, 즉 배낭 무게가 0일 때
## 고려사항
첫번째 물건인 경우를 살펴보자.
무게가 6, 가치가 13인 물건을 넣을지 안넣을지 생각할 것.
그런데 넣을지 안넣을지 고민하는건 저 보라색 부분에서만 가능한 것 아니겠는가?
아니 ~ 적어도 배낭 무게가 6이상이어야만 , 현재 물건을 넣는 것을 의미하잖아 !!
그럼 j가 6미만 인 부분은 고려하지 않아도 된다.
그러니, 초록색 부분과 같이 해당 물건을 넣지 않는 값.
즉, i-1 값을 그대로 가져오면 된다.
그 후, 이제 보라색 부분을 고려해보자.
그 중 dp[1][6] 보라색 부분 을 구해보자.
해당 물건을 포함하지 않을 때 : dp[i-1][j] 인 경우
=> 이건 이해가 쉬울 것이다.
해당 물건을 포함할 때는 결론 부터 이야기 하자면
해당 물건 넣기 전 가치 + 해당 물건 가치 가 된다.
식으로 나타내면 "dp[i-1][j-w] + v" 인데, 나눠서 살펴보자.
- i-1: 해당 물건 넣기 전 상태에서 확인을 한다.
- j-w: 현재 j는 6인데, 해당 물건을 넣기 전을 알고 싶다면, 해당 물건 6을 뺐을 때의 상태를 봐야 한다.
- v : 해당 물건 가치
정답 코드
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const [n,k] = input.shift().split(' ').map(v => +v);
let arr = [];
for(let i=0; i<n; i++){
arr.push(input[i].split(' ').map(v => +v))
}
function solution(n,k,arr){
let answer = 0
let dp = Array.from({length: n+1}).map(() => new Array(k+1).fill(0))
for(let i=1; i<n+1; i++){
let [w,v] = arr[i-1]
for(let j=1; j<k+1; j++){
if(j >= w){
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w] + v)
answer = Math.max(answer, dp[i][j])
}else{
dp[i][j] = dp[i-1][j]
}
}
}
return answer
}
console.log(solution(n,k,arr))