[BAEKJOON] 1660 캡틴 이다솜

#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 풀었던 것처럼

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