728x90
반응형

이 문제는 DP문제이다.
0부터 n까지 k개를 더해서 n이 되는 경우의 수를 구하는 것이며, 덧셈의 순서가 바뀐 경우는 다른 경우로 센다.
그리고 한개의 수를 여러번 쓸 수 있다.
n은 2고 k는 2이라고 예를 들어보자.
k |
n |
n을 구하기 위한 과정 |
1 |
0 |
0 경우의 수 : 1개 |
1 |
1 |
1 경우의 수 : 1개 |
1 |
2 |
2 경우의 수 : 1개 |
2 |
0 |
0 0 경우의 수 : 1개 |
2 |
1 |
0 1 1 0 경우의 수 : 2개 |
2 |
2 |
0 2 1 1 2 0 경우의 수 : 3개 |
따라서 3개라는 것을 알 수 있다.
여기서 알아야할 것은 n을 구하기 위해서는 사실
k |
n |
n을 구하기 위한 과정 |
1 |
0 |
0 경우의 수 : 1개 |
1 |
1 |
1 경우의 수 : 1개 |
1 |
2 |
2 경우의 수 : 1개 |
2 |
0 |
0 0 경우의 수 : 1개 |
2 |
1 |
0 1 1 0 경우의 수 : 2개 |
2 |
2 |
0 2 1 1 2 0 경우의 수 : 3개 |
주황색으로 표시된 값의 경우의 수만 알아도 된다는 것이다.
즉 dp[i][1] 만 알아도 된다는 것이다.
왜냐하면 구하고자 하는 값 - i 로 설정되기 때문이다.
이것을 점화식으로 표현하면
dp[n][k] = dp[n - 1][k - 1] + dp[n - 2][k - 1] + ... + dp[0][k - 1]
이렇다.
코드로 표현해보면
// 합분해
#include <iostream>
using namespace std;
int main(void){
int n,k,dp[201][201] = {1};
cin >> n >> k;
for(int i = 0; i <= n; i++){
for(int j = 1; j <= k; j++){
for(int l = 0; l <= i; l++){
dp[i][j] = (dp[i][j] + dp[i - l][j - 1]) % 1000000000;
}
}
}
cout << dp[n][k] % 1000000000;
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 수 이어 쓰기 1 (0) | 2020.11.03 |
---|---|
[algorithm] 백준 - 가장 긴 바이토닉 부분 수열 (0) | 2020.11.03 |
[algorithm] 백준 - 제곱수의 합 (0) | 2020.11.03 |
[algorithm] 백준 - 연속합 2 (0) | 2020.11.03 |
[algorithm] 백준 - 가장 긴 증가하는 부분 수열 1 & 4 (0) | 2020.11.03 |