반응형
https://www.acmicpc.net/problem/2225
2225번: 합분해
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
[ 문제풀이 ]
1. 점화식 dp [ i ][ j + k ] += dp [ i - 1 ][ j ]를 통해 각 위치에서의 최댓값을 저장합니다.
2. 최댓값을 1,000,000,000으로 모듈러 연산을 한 값을 dp배열에 저장합니다.
3. dp[ K ][ N ] 을 출력합니다
[ 소스코드 ]
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 | #include<iostream> #define M 1000000000 using namespace std; int N, K; int dp[201][201]; int main() { scanf("%d %d", &N, &K); for (int i = 0; i <= N; i++) { dp[1][i] = 1; } for (int i = 2; i <= K; i++) { for (int j = 0; j <= N; j++) { for (int k = 0; k <= N; k++) { if (j + k <= N) { dp[i][j + k] += dp[i-1][j]; dp[i][j + k] %= M; } } } } printf("%d", dp[K][N]); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2133번 - 타일 채우기 (C++) (0) | 2022.10.23 |
|---|---|
| [ 백준 ] 5582번 - 공통 부분 문자열 (C++) (0) | 2022.10.22 |
| [ 백준 ] 2011번 - 암호코드 (C++) (0) | 2022.10.20 |
| [ 백준 ] 2631번 - 줄세우기 (C++) (0) | 2022.10.19 |
| [ 백준 ] 2636번 - 치즈 (C++) (0) | 2022.10.16 |