백준11052 카드 구매하기

문제

풀이

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

int main() {

    int *arrx;
    int input;
    int i = 0;
    int m, n;
    int *arry;
    int max=0;

    cin >> input;
    arrx = new int[input+1];
    arry = new int[input+1];
    arrx[0] = 0;
    arry[0] = 0;

    for (i = 1; i <= input; i++) {
        cin >> arrx[i];
        arry[i] = 0;
    }

    for (m = 1; m <= input; m++) {
        for (n = 1; n <= input; n++) {
            if (m - n >= 0)
                if (max < arry[m - n] + arrx[n])
                    max = arry[m - n] + arrx[n];
        }
        arry[m] = max;
        max = 0;
    }
    cout <<arry[input];

    return 0;
}

풀이방법

간단한 다이나믹 프로그래밍이다.
예를 들어
카드가 2장 있으면 1+1
3장 있으면 max(1+2,3)
4장 있으면 max(1+3,2+2,4)
이런식으로 구해주면 끝!