23.03.23 / DP

11052번: 카드 구매하기 (acmicpc.net)

 

연관 페이지 : 22.10.21/ DP :: 쥔다의 개발 여행길 (tistory.com)

 

DP의 핵심은 '재사용'이다. 구현 방법은 '배열' 이며, 배열의 값을 재사용하는 것을 핵심으로 둔다. ↑DP의 대표적인 예시인 피보나치 수열 F0​=0, F1​=1, Fn+2​=Fn+1​+Fn​

DP 문제인지 파악 ↓ 관계식 만들기 (점화식) ↓ 배열로 변수 정의 ↓ 기저 상태 정의 (가장 낮은 최후 값) ↓ Bottom-Up 반복문 or Top-Down 재귀문

Bottom-Up : 반복문 구현- 아래(기저)에서 누적시켜 전체 큰 문제 해결.  Top-Down : 재귀문 구현- n에서 출발하여 기저상태까지 재귀 수행.

 

알고리즘 :
모든 경우의 수를 확인하여 값을 저장한다. (점화식을 찾는다)

문제점 :
처음엔 점화식을 a_n = a_n-1 + a_1 로 두고 풀었으나 이 식이 모든 경우를 표현하지 못함을 깨달아서
다른 풀이를 보게되었다.
예)
4
= (3) + 1
= (2 + 1) + 1
= ((1 + 1) + 1) + 1
의 경우만 있는 것이 아닌
4 = 2 + 2 같은 경우도 존재함.

 

다른 풀이 :
다른 풀이의 점화식만을 참고해 풀어보았다.
[C++] 백준 11052 - 카드 구매하기 (tistory.com)

카드 N개를 살때 총 경우는
dp[N] = 카드 N개의 가격
dp[N] = 카드1개의 살때의 최대가격 + 카드 N-1개의 가격
dp[N] = 카드2개의 살때의 최대가격 + 카드 N-2개의 가격
...
로 한 dp[N]의 식에 여러가지 경우를 체크해봐야한다.

 

그러므로 점화식은 2가지의 경우
즉, 다른 dp[N]의 경우와 현재 체크하려는 값 중의 최대값이다.
dp[N] = Math.max( dp[N], dp[N-i] + card[i] )

// 입력 값
const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const n = parseInt(input[0]);
const card = input[1].trim().split(" ").map(element=> {return parseInt(element)});
// n : 카드 개수 N, card : Pi 리스트

//풀이 ―――
let dp = new Array(n);
for(let i = 0; i < n; i++)
  dp[i] = card[i];

// dp[N-i] 꼴의 값을 구해야하므로 Bottom-Up 방식으로 접근한다
for(let i = 0; i < n; i++)
  for(let j = 0 ; j < i; j++)
    dp[i] = Math.max(dp[i], dp[i-1-j] + card[j]);

console.log(dp[n-1]);

중요한 점 :
DP의 경우 예시를 보고 패턴을 찾아 점화식을 정확히 찾아내는 것이 중요하다.
점화식의 경우 여러개의 식을 체크해봐야할 수도 있다.

 

추가 사항 :

let dp = new Array(n); for(let i = 0; i < n; i++)   dp[i] = card[i];

→

// spread 연산자를 통해 배열 초기화 가능 let dp = […card]