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

문제링크 : https://www.acmicpc.net/problem/16194

16194번: 카드 구매하기 2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int arr[1001];
int dp[1001];

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

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

    for(int i=1; i<=N; i++)
    {
        dp[i] = arr[i]; //i장 살때 i장든 팩을 삼 (초기화)
        for(int j=1; j<i; j++)
        {
            dp[i] = min(dp[i], dp[i-j] + dp[j]); //i장 살때 i장 만큼 사는 것이 나은가, 다른 팩으로 나눠서 사는게 나은가
        }
    }

    cout << dp[N];


    return 0;
}

DP 문제이다.

 

N장 만큼을 살때, N장이 든 팩을 바로 사는 것이 저렴한지, 아니면 다른 팩들로 나눠서 사는게 저렴한지를 비교한다.

 

ex) N : 4

1 1 1 1 

1 2

2 2

1 3