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

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

11052번: 카드 구매하기

> 풀이

 

동적 계획법를 이해하고 있다면 바로 풀 수 있는 문제인것 같습니다. 정답률이 60프로네요?

 

dp[n]을 n개의 카드를 구입할 때 최대 가격이라고 가정한다면

 

dp[n] = P1 + dp [n - 1] , P2 + dp [n - 2] .... Pn + dp [0] 중 최대값이 되겠죠?

#include <bits/stdc++.h>
using namespace std;

int dp[1001];
int price[1001];
int N, res;

int main(void) {
        scanf("%d", &N);
        for (int i = 1; i <= N; i++) scanf("%d", &price[i]);

        dp[1] = price[1];

        for (int n = 2; n <= N; n++) {
                res = 0;
                for (int i = 1; i <= n; i++) {
                        res = max(res, dp[n - i] + price[i]);
                }
                dp[n] = res;
        }

        printf("%d", dp[N]);
        return 0;
}