백준 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))