[백준][BOJ] 카드 구매하기 - silver.1 | 자바스크립트 | 동적계획법 (Dynamic progrmming, DP)

문제

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

11052번: 카드 구매하기

 

풀이

function solution(N, price){
    let dp = [0, ...price];
    for(let i = 2; i <= N; i++){
        for(let j = 1; j < i; j++)
            dp[i] = Math.max(dp[i], dp[j] + dp[i - j]); // j + (i-j) = i이기 때문에, i 개의 카드를 뽑기 위한 조합 별로 j를 증가시켜서 최댓값을 계속 업데이트해준다.
    }
    return dp[N];
}

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input[0];
const price = [...input[1].split(' ')].map((el) => +el);
console.log(solution(N, price))

처음에 일일이 N개를 뽑을 수 있는 조합의 경우 수를 다 구했는데, 아무리봐도 좀 더 쉽게 풀 수 있을 것 같았다.

위 코드는 각 i마다 i개씩 뽑을 수 있는 경우의 수 별로 최댓값을 계속 업데이트 해주는 방법이다.
i = 2일 때, j는 1로 한번 반복될 수 있고(조건이 j < i 이기 때문) 기존의 원래 값( dp[i] ) 보다 dp[j] + dp[i-j] 가 더 크다면 업데이트 된다.

입력 배열(price)의 1번째 인덱스에는 1장 짜리 카드의 금액이 들어있고, 2번째에는 2장 짜리 카드의 금액, 3번째에는 3장 짜리 카드의 금액 •••  쭉쭉 들어있는데,
i = 3 일때는 j가 1, 2 로 2번 반복되고, dp[j] + dp[i-j] 에서 보면
" j = 1 : 1번째 + 2(3-1)번째 더한 값,
  j = 2 : 2번째 + 1(3-2)번째 더한 값 " 을 각각 기존 값과 비교해서 더 큰 경우 업데이트 해주게 된다.

결국, i 개 반복마다 j 반복에서 맨 처음인 1부터 높은 인덱스 방향으로 올라가는 값과 i에서 j씩 빼주면서 낮은 인덱스 방향으로 내려오는 값을 더하면 그 둘은 합이 i개가 되기 때문에 "2개를 뽑는 경우 최댓값, 3개를 뽑는 경우 최댓값 ••• N개를 뽑는 경우 최댓값" 이 쭉쭉 계산돼서 dp[N]에는 N개를 뽑을 때 최댓값이 들어가게 된다.

dp[1] : 1개를 뽑을 때 최댓값
dp[2] : 2개를 뽑을 때 최댓값
••• 
dp[N] : N개를 뽑을 때 최댓값

어렵다 어려워..^^