https://www.acmicpc.net/problem/2225
[2225번: 합분해
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net](https://www.acmicpc.net/problem/2225)
문제가 말하는 대로 합분해를 해보았다.
예를 들어서 0부터 6까지의 정수들 중에 2개를 사용해 6을 만든다고 했을 때 다음과 같은 조합이 나온다.
0 6
1 5
2 4
3 3
4 2
5 1
6 0
여기서 더 나아가 0부터 6까지의 정수들 중에 3개를 사용해 6을 만든다고 했을 때, 다음과 같은 조합을 볼 수 있다.
0 0 6
0 1 5
0 2 4
0 3 3
0 4 2
0 5 1
0 6 0
1 0 5
1 1 4
1 2 3
1 3 2
1 4 1
1 5 0
2 0 4
2 1 3
...
근데 살펴보면 바로 직전에 0부터 6까지의 정수들 중 2개를 사용했을 때 만들었던 조합이 보인다.
이걸 생각해보면 제일 앞자리의 숫자를 바꿔가면서 조합을 찾을 때 이미 구했던 조합들을 활용해볼 수 있다는 것이다.
S(N, K) = 0부터 N까지의 정수들 중 K개를 사용해 N을 만들 수 있는 조합의 수
S(N, K)를 위처럼 정리해두어보면 S(6, 3)은 S(6, 2) + S(5, 2) + S(4, 2) ... + S(0, 2) 임이 보인다.
제일 앞자리의 숫자를 바꾸면서 재귀식을 돌리면 되는데, 메모이제이션을 통해 연산을 최소화시키면 된다.
#include <iostream>
int dp[201][201]{ 0 };
int S(int n, int k) {
if (k == 1) {
return 1;
}
if (dp[n][k]) {
return dp[n][k];
}
for (int i = n; i >= 0; i--) {
dp[n][k] = (dp[n][k] + S(i, k-1)) % 1000000000;
}
return dp[n][k];
}
int main() {
int N, K;
scanf("%d %d", &N, &K);
printf("%d", S(N, K));
}
'프로그래밍 > 알고리즘' 카테고리의 다른 글
9020 골드바흐의 추측 (0) | 2022.08.19 |
---|---|
11653 소인수분해 (0) | 2022.08.19 |
1018 체스판 다시 칠하기 (0) | 2022.08.19 |
2293 동전 1 (0) | 2022.08.17 |
11726 2xN 타일링 (0) | 2022.08.16 |
댓글