백준 16194 카드 구매하기 2 (C++)

16194번: 카드 구매하기 2

dp를 이용한 문제이다. 주어진 N만큼 반복문을 돌면서 1부터 i-1까지 값들을 비교를 해서 최솟값을 dp에 저장해준 뒤 출력해주었다. 쉽게 풀 수 있었던 문제였다.

#include <iostream>

using namespace std;

int N;
int P[10001];
int dp[10001];

void solution() {
    dp[1] = P[1];

    for (int i = 2; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            dp[i] = min(dp[i], dp[i - j] + P[j]);
        }
    }

    cout << dp[N];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 1; i <= N; i++) {
        cin >> P[i];
        dp[i] = P[i];
    }

    solution();

    return 0;
}