[BAEKJOON] 1660 캡틴 이다솜

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include <iostream> #include <vector> #include <algorithm> #define MAX 987654321 #define SUMCOUNT 130 using namespace std;   int main() {     vector<int>sum(SUMCOUNT, 0);     vector<int>dp(300001, MAX);       int diff = 2, num = 1, N;       sum[0] = 1;     for (int j = 1; j < SUMCOUNT; j++)     {         num += diff++;         sum[j] = sum[j - 1] + num;         if (sum[j] >= 300000) break;     }       cin >> N;       for (int j = 0; j < SUMCOUNT; j++)     {         if (sum[j] >= 300000) break;           dp[sum[j]] = 1;                   for (int k = sum[j] + 1; k <= N; k++)             dp[k] = min(dp[k], dp[k - sum[j]] + 1);     }       cout << dp[N] << endl;       return 0; }

음..문제를 이해하는데..시간이 좀 걸렸다..

그냥 동전 2 풀었던 것처럼

목표치를 주고 그거에 맞는 최소 개수를 출력하면 된다