✅ DP

문제

링크

1. 문제 접근 및 해결 로직

$f(N)$ : $N$개의 카드를 살 때의 최대 금액,
$price[N]$ : $N$번째 카드팩의 가격 이라고 하자.

• $N=1$
  $price[1]$

• $N=2$
  =1+1
  =2
  둘 중에 총 금액이 큰 경우
  $f(2)=max(f(1)+f(1),price[2])$

• $N=3$
  =1+1+1
  =1+2
  =3
  셋 중에 총 금액이 큰 경우
  $f(3)=max(f(1)+f(1)+f(1),f(1)+f(2),price[3])$

• $N=4$
  =1+1+1+1
  =1+1+2
  =2+2
  =1+3
  =4
  셋 중에 총 금액이 큰 경우
  $f(4)=max(f(1)+f(1)+f(1)+f(1),f(1)+f(1)+f(2),f(2)+f(2),f(3)+f(1),price[4])$

이런 식인데 규칙을 찾기가 너무 어렵다..
다른 문제들 처럼 맨 마지막을 기준으로 앞의 값을 이용하는 쪽으로 생각해보자.

1) 마지막에 1개짜리 카드팩을 구매하는 경우
마지막에 1개짜리 카드팩을 구매한다고 가정하면, 그 전에서 N-1개의 카드를 구매해야 하고, 이를 식으로 나타내면 $f[N-1] + price[1]$ 이 된다.
2) 마지막에 2장짜리 카드팩을 구매하는 경우
마지막에 2개짜리 카드팩을 구매한다고 가정하면, 그 전에서 N-2개의 카드를 구매해야 하고, 이를 식으로 나타내면 $f[N-2] + price[2]$가 된다.
...
N) 마지막에 N장짜리 카드팩을 구매하는 경우
마지막에 N개짜리 카드팩을 구매한다고 가정하면, 그 전에서 N-N개의 카드를 구매해야 하고, 이를 식으로 나타내면 $f[N-N] + price[N]$ 이 되게 된다.

최대비용을 구해야 하므로, 마지막에 카드를 1장 사는 것 부터 최대 N장 사는 모든 경우 중에 최댓값을 구해야 한다.

• 정의
  $f(N)$ : $N$개의 카드를 살 때의 최대 금액
  $f(N)$ : $N$번째 카드팩의 가격
• 구하는 답
  $max(f[N-1] + price[1], f[N-2] + price[2],...,f[N-N] + price[N])$
• 초기값
  $f(1)=price[1]$
• 점화식
  $f[N-i] + price[i]$

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항