[백준] 합분해
2021. 7. 14. 05:28ㆍ알고리즘 관련/DP
합분해(골 5) : https://www.acmicpc.net/problem/2225
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제.
즉, n = 3, k = 2가 주어지면,
(0, 3) (1, 2) (2, 1) (3, 0)의 네 가지 경우의 수를 구할 수 있음.
1. 문제 분석
경우의 수를 모두 구하는 문제니, 최적화 문제는 아님.
for문 돌면서 k가 1씩 감소하면서 재귀 호출을 하면 될 것 같음!
2. 완전 탐색 구현
#include <iostream>
using namespace std;
int disassemble(int n, int k)
{
if (k == 0)
{
if (n)
return 0;
return 1;
}
int cnt = 0;
for (int num = 0; n + 1 > num; num++)
{
if (n - num < 0)
continue;
cnt += disassemble(n - num, k - 1) % 1000000000;
}
return cnt;
}
int main(void)
{
int N, K;
cin >> N;
cin >> K;
cout << disassemble(N, K) << '\n';
return 0;
}
n과 k가 조금만 커져도, 재귀 중복호출이 많이 일어나고, 경우의 수 자체가 기하급수적으로 커진다. 따라서, int -> long long으로 바꾸고, DP화를 하여 시간을 단축시킬 수 있다.
3. DP화
메모리제이션 구현 레시피(https://sanghoonly.tistory.com/29)대로 DP화 완료!
#include <iostream>
#include <memory.h>
using namespace std;
long long cache[201][201];
long long disassemble(long long n, long long k)
{
if (k == 0)
return 1;
long long &ret = cache[n][k];
if (ret != -1)
return ret;
long long cnt = 0;
for (long long num = 0; n + 1 > num; num++)
{
if (n - num < 0)
continue;
if (k - 1 == 0 && n - num != 0)
continue;
cnt += (disassemble(n - num, k - 1));
}
return ret = cnt % 1000000000;
}
int main(void)
{
long long N, K;
cin >> N;
cin >> K;
memset(cache, -1, sizeof(cache));
cout << disassemble(N, K) << '\n';
return 0;
}
'알고리즘 관련 > DP' 카테고리의 다른 글
[백준] 1, 2, 3 더하기 3 (0) | 2021.07.14 |
---|---|
[백준] 최대 증가 부분 수열(LIS) 문제 (0) | 2021.07.14 |
[백준] 제곱수의 합 (0) | 2021.07.14 |
[백준] 1로 만들기 (0) | 2021.07.06 |
[백준] 2 x n 타일링 (0) | 2021.07.06 |