[백준_DP] 11052 카드 구매하기 ( by using javascript )

문제

접근법

본격적으로 DP 문제를 풀면서, 본 문제보다 낮은 단계의 문제들에서는 보통 이전 값들을 더하는 방식으로 결과값을 구했었다.

그리하여, 점화식 설계의 큰 어려움을 겪지 못했는데 "카드 구매하기" 같은 경우는 N개의 카드를 가장 비싼 값에 사기 위해서는 

모든 경우의 수를 비교하는 과정이 필요했다.

 

그리하여 loop를 통한 접근을 당연시 하다고 느껴서 도입을 했음에도 불구하고 루프 안에서 i, j 와 같은 변수를 이용 하지 않았기 때문에 해결하는데 큰 어려움을 겪었다.

 

 

루프 안에서 변수를 사용 하지 않았다는게 무엇을 의미하는걸까?

 

for ( let i = 1; i < n; i++ ) {

	for ( let j = 1; j < n; j++ ) {
    
    }

}

위의 코드처럼 변수에 특정 값을 대입하여, 우리가 정해놓은 목표치 까지 도달하는 것을 의미하는데 이렇게 되면 

 

n장의 카드의 최대 값을 구하기 위해, 모든 수를 비교하는 작업이 불가능해진다.

 

 

 

그리하여, 아래와 같이 j의 max 값을 능동적으로 변경 + j 루프 안에서 i를 사용하는 방법을 통해 이를 해결하였다.

for (let i = 1; i <= n; i++) {
  dp[i] = 0;
  for (let j = 1; j <= i; j++) {
    dp[i] = Math.max(dp[i], dp[i - j] + cards[j]);
  }
}

 

코드

let input = require("fs").readFileSync("dev/stdin").toString().split("\n");
let n = Number(input[0]);
const cards = input[1].split(" ").map(Number);
cards.unshift(0);

const dp = [0];

for (let i = 1; i <= n; i++) {
  dp[i] = 0;
  for (let j = 1; j <= i; j++) {
    dp[i] = Math.max(dp[i], dp[i - j] + cards[j]);
  }
}

console.log(dp[n]);

 

느낀점

난이도가 올라감에 따라, 기존에 사용했던 "기본"적인 것들을 응용 해야 풀 수 있다는 것을 배우고 있다.