[알고리즘] 카드 구매하기

구현 방식

• k 개의 카드를 살때의 최대 이익을 acc[k]에 담는다고 할때 아래와 같은 점화식을 얻을 수 있다.

acc[k] = max(p[k] , acc[k-i] + acc[i])

코드

• 최종 코드는 아래와 같다.

int prices[1001] = {};
int acc[1001] = {};

int main()
{
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> prices[i];
        acc[i] = prices[i];
    }
    solution(N);
}


void solution(int N)
{
    cout << dp(N);
}

int dp(int N)
{
    for (int k = 2; k <= N; k++)
    {
        for (int i = 1; i < k; i++)
        {
            acc[k] = max(acc[k], acc[k - i] + acc[i]);
        }
    }
    return acc[N];
}