알고리즘 문제풀이
[백준/BOJ] 백준 2225번 : 합분해
GeniusJo
2020. 12. 26. 12:01
2225번: 합분해
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
덧셈의 순서가 바뀐 경우도 다른 경우로 세고, 수를 여러 번 쓸 수 도 있으므로 숫자를 더해가는 경우(기저 사례가 아닌 경우)일 때 숫자 0부터 n까지를 확인하여 해당 수를 더한 경우를 확인한다. cache[sum][num]은 현재까지 합이 sum이고 숫자 num개를 사용했을 때 계산한 적이 있다면 중복해서 계산하지 않고 계산했던 값을 사용한다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
int n, k;
int cache[201][201];
//초기화
void Pre()
{
for (int i = 0; i < 201; i++)
for (int j = 0; j < 201; j++)
cache[i][j] = -1;
}
int Solve(int sum, int num)
{
//k개를 더했을때
if (num == k)
{
//그 합이 n일때
if (sum == n)
return 1;
else
return 0;
}
//합이 n보다 클때
if (sum > n)
return 0;
//개수가 k보다 클때
if (num > k)
return 0;
int& ret = cache[sum][num];
if (ret != -1)
return ret;
ret = 0;
//숫자 0부터 n까지 확인
for (int i = 0; i <= n; i++)
{
ret += Solve(sum + i, num + 1);
ret %= 1000000000;
}
return ret;
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> k;
Pre();
cout << Solve(0, 0);
return 0;
}