[BAEKJOON] 2410 2의 멱수의 합

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <math.h> using namespace std; int main() { int n, num; scanf("%d", &n); vector<long long>dp(n + 1, 0); for (int j = 0; j <= 100; j++) { num = pow(2, j); if (num > n) break; dp[num] = (dp[num] + 1) % 1000000000; for (int k = 1; k + num <= n; k++) dp[k + num] = (dp[k + num] + dp[k]) % 1000000000; } printf("%lld", dp[n]); return 0; }

동전1을 이용하면 된다

안전하게 long long으로 했다.