[BAE/<JOON> 문제풀이] 1660. 캡틴 이다솜

https://www.acmicpc.net/problem/1660

1660번: 캡틴 이다솜

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> coin;
    vector<int> dp;            
    coin.push_back(0);
    int c = 1;
    for (int i = 1; c <= n; i++) {
        int s = 0;
        for (int j = 1; j <= i; j++) {
            s += j;
        }
        c = s + coin[coin.size() - 1];
        coin.push_back(s + coin[coin.size() - 1]);
    }

    int cs = coin.size( ) - 1;

    //dp.resize(n + 1);
    dp.assign(n + 1, 2000000000);
    dp[0] = 0;
    //dp[0].resize(n + 1);
    /*for (int i = 0; i <= cs; i++) {                            
        dp[i].assign(n + 1, 2000000000);
        dp[i][0] = 0;
    }*/

    for (int i = 1; i < cs; i++) {
        /*for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
        }*/
        for (int j = coin[i]; j <= n; j++) {
            int p = min(dp[j], dp[j - coin[i]] + 1);
            dp[j] = p;
        }
    }

    /*for (int i = 1; i <= n; i++) {
        cout << dp[i] << " ";
    }*/
    /*for (int i = 1; i <= cs; i++) {
        for (int j = 1; j <= n; j++) {
            if (dp[i][j] == 20000000) {
                cout << "0 ";
                continue;
            }
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }*/

    /*int mn = dp[1][n];
    for (int i = 2; i < cs; i++) {
        mn = min(mn, dp[i][n]);
    }*/
    cout << dp[n] << "\n";
    return 0;
}