백준 11052번 카드 구매하기 (C++)

문제 링크 : www.acmicpc.net/problem/11052

11052번: 카드 구매하기

문제 풀이는 다음과 같다. 

1. 1부터 n까의 카드값 배열을 입력 받는다.

2. 카드값 배열의 0번째 원소는 0으로 초기화해준다.

3. 2중 for문을 세운다. 아래 이중 for문의 해석은 다음과 같다.

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

예를들어 3개의 카드를 구하는 최대값을 구해보자.

arr[3]은 arr[3] vs arr[1]+arr[2] or arr[2]+arr[1] or arr[3]+arr[0] 에서 최대값이 나오는 값으로 선정된다.

마찬가지로 5개의 카드를 구하는 최대값을 구해보자.

arr[5]는 arr[5] vs arr[1]+arr[4] or arr[2]+arr[3] or arr[3]+arr[2] or arr[4]+arr[1] or arr[5]+arr[0] 에서 최대값이 나오는 값으로 선정된다. 이를 통해 우리는 어느 n개의 숫자를 나오기 위한 모든 종류의 점화식을 테스트 할 수 있다.

 

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, arr[1001];
    cin >> n;
    arr[0] = 0;
    for(int i=1; i<=n; i++) cin >> arr[i];
    for(int i=2; i<=n; i++){
        for(int j=1; j<=i; j++){
            arr[i] = max(arr[i],arr[j]+arr[i-j]);
        }
    }
    cout << arr[n] << "\n";
    return 0;
}

처음 도전했을때는 틀렸는데, 이유를 보니 DP를 위한 점화식을 세운게 아닌, 그저 답을 구하기 위한 모든 경우의 수를 덕지덕지 갖다 붙였기 때문이었다. DP문제는 최대한 답이 깔끔하게 나와야 정답에 가까워지는 느낌이 든다.