728x90
https://www.acmicpc.net/problem/2225
문제
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
코드
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
int N,K;
vector<int> num;
long long cache[201][201];
long long getSum(int toPick, int sum){
if(sum < 0){
return 0;
}
if(toPick == 0){
if(sum == 0){
return 1;
}
return 0;
}
long long& ret = cache[sum][toPick];
if(ret != -1){
return ret % 1000000000;
}
ret = 0;
for(int i=0; i<=N; ++i){
ret += getSum(toPick-1, sum-num[i]) % 1000000000;
}
return ret % 1000000000;
}
int main(void){
memset(cache, -1, sizeof(cache));
cin >> N >> K;
for(int i=0; i<=N; ++i){
num.push_back(i);
}
cout << getSum(K, N) % 1000000000;
}
dp 문제이다.
이번 문제는 간단한 dp 문제라 재귀로 풀었다.
항상 강조하는게 재귀 dp 는 top to bottom이라 거꾸로 이해해서 풀어야 한다.
여기서도 sum을 N으로 두고 시작해 깎아 내리는 식으로 풀었다.
답을 몇으로 나누라는 문제들은 어짜피 (A+B) % N = A%N + B%N이기 때문에 용량 초과가 날거 같은 곳에 다 % N을 해주면 대충 맞는다.
728x90
반응형
'PS > DP' 카테고리의 다른 글
[14501] 퇴사 (0) | 2023.07.03 |
---|---|
[2133] 타일 채우기 (0) | 2023.06.27 |
[2294] 동전 2 (0) | 2023.06.27 |
[11054] 가장 긴 바이토닉 부분 수열 (0) | 2023.04.29 |
[11053] 가장 긴 증가하는 부분 수열 (0) | 2023.04.16 |