(C++) 백준 2225 합분해
문제 및 풀이
https://www.acmicpc.net/problem/2225
- 0개 더해서 i가 되는 경우의 수는 1가지!
- 1개 더해서 i가 되는 경우의 수는 1가지
- 2개 더해서 i가 되는 경우의 수
- 1개 더해서 i-1 되는 수 + 1 == 2개 더해서 i되는 수
- 1개 더해서 i-2 되는 수 + 2 == 2개 더해서 i되는 수
- 1개 더해서 i-3 되는 수 + 3 == 2개 더해서 i되는 수
- .....
- 1개 더해서 i되는 수 + 0 == 2개 더해서 i되는 수
즉, 이를 일반화하면 k개 더해서 n이 되는 수 dp[k][n]는
dp[k][n] = dp[k-1][0] +....... dp[k-1][n]
코드
#include <iostream>
#define ll long long
using namespace std;
const ll MOD = 1000000000;
ll dp[205][205];
int main(){
int N,K; cin>>N>>K;
for(int i=0; i<=N; i++) dp[1][i]=1;
for(int k=2; k<=K; k++) {
for(int x=0; x<=N; x++){
for(int i=0; i<=x; i++){
dp[k][x] += dp[k-1][i];
if(dp[k][x]>MOD) dp[k][x]-=MOD;
}
}
}
cout<<dp[K][N];
}
Author And Source
이 문제에 관하여((C++) 백준 2225 합분해), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minayeah/C-백준-2225-합분해저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)