반응형
https://www.acmicpc.net/problem/2410
2410번: 2의 멱수의 합
첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
[ 문제풀이 ]
1. $dp[$ $i$ $]$ 는 i의 수를 만들기 위한 경우의 수입니다.
2. $dp[$ $i$ $]$ 는 $dp[$ $i$ $-$ $2^{x}$ $]$ 값들에 $2^{x}$를 더한 값이므로 모든 $dp[$ $i$ $-$ $2^{x}$ $]$ 값들을 더해주면 $dp[$ $i$ $]$가 됩니다.
3. $dp[$ $i$ $]$ += $dp[$ $i$ $-$ $2^{x}$ $]$의 점화식을 사용하여 dp배열을 채워줍니다.
[ 소스코드 ]
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 | #include<iostream> #define M 1000000000 using namespace std; int N; int dp[1000001]; int main() { scanf("%d", &N); dp[0] = 1; for (int i = 0; i <= 20; i++) { for (int j = 1; j <= N; j++) { if ((j - (1 << i)) >= 0) { dp[j] += dp[j - (1 << i)] % M; dp[j] %= M; } } } printf("%d", dp[N]); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 9461번 - 파도반 수열 (C++) (0) | 2022.10.27 |
|---|---|
| [ 백준 ] 2579번 - 계단 오르기 (C++) (0) | 2022.10.26 |
| [ 백준 ] 2228번 - 구간 나누기 (C++) (0) | 2022.10.24 |
| [ 백준 ] 2133번 - 타일 채우기 (C++) (0) | 2022.10.23 |
| [ 백준 ] 5582번 - 공통 부분 문자열 (C++) (0) | 2022.10.22 |