BOJ 11052 카드 구매하기

boj 11052 카드 구매하기

- 문제 링크

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

- 문제 해설

DP가 작은 문제부터 쌓아나가서 구하고자 하는 값을 구하는 알고리즘임을 생각하면 쉽게 접근 방법을 찾을 수 있다. 나는 보통 DP로 문제를 풀 때 D[i]를 어떻게 나눌지를 생각하는 편이다.

D[i]를 i개의 카드를 사는 금액의 최댓값이라고 지정하자. 그러면 아래와 같이 쪼갤 수 있다.

• D[i-1] + P[1] : 카드 1개가 들어있는 팩의 구매 값 + i-1개의 카드를 구매한 최댓값
• D[i-2] + P[2] : 카드 2개가 들어있는 팩의 구매 값 + i-2개의 카드를 구매한 최댓값
  .
  .
  .
• D[0] + P[i] : 카드 i개가 들어있는 팩의 구매 값 + 0개의 카드를 구매한 최댓값

이것들을 전부 비교해서 그 중 최댓값이 D[i]가 된다.
즉, 점화식은 D[i] = max(D[i], D[i-j] + P[j]) (1<=j<=i) 이다.

- 코드 보기

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int P[1005];
int D[1005];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> P[i];

    D[1] = P[1];

    for (int i = 2; i <= n; i++)
    {    
        for (int j = 1; j <= i; j++)
        {
            D[i] = max(D[i], D[i - j] + P[j]);
        }
    }

    cout << D[n];
}