문제링크
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으로 나눈 나머지를 출력한다.
조건
- 시간 제한 : 2s
- 메모리 제한 : 128MB
해설
N이 8이라고 가정하고 K에 따른 경우의 수를 구해보면 아래와 같다.
K = 1 >> 1
8
K = 2 >> 9
0 8 / 1 7 / 2 6 / 3 5 / 4 4 / 5 3 / 6 2 / 7 1 / 8 0
K = 3 >> 45
0 0 8 / 0 1 7 / ... / 0 8 0 / 1 0 7 / ... / 1 7 0 / 2 6 0 / ...K가 3 이상일 때를 보면 첫번째 수가 0일때는 K=2일 때 N=8의 경우의 수, 첫번째 수가 1일때는 N=7의 경우의 수, ... 와 같은 방식으로 더해진다. 이를 나는 아래와 같은 방식으로 나타냈다.
K = 1
1
K = 2
9
K = 3
9+8+7+...+1
K = 4
(9+8+7+...+1) + (8+7+...+1) + ... + (2+1) + (1)
K = 5
{(9+...+1)+ ... +(1)} + {(8+...+1)+ ... +(1)} + ... + {(1)}
여기에서 내가 찾은 규칙은 K=k일 때 k-1의 값에서 앞에서부터 괄호묶음이 하나씩 빠지면서 더해진다는 것이다.
풀이
아래와 같이 DP를 만들어 나가는 과정을 계획하였다. i번째 행에 대해 계산한다고 할 때, i-1번째 행의 원소의 합을 sum이라 하자. 이 값이 dp[i][0]의 값이 되고, dp[i][j] = dp[i][j-1] - dp[i-1][j-1]의 식을 만족한다.
DP
0 : 0 0 0 0 0 0 0 0 0
1 : 1 1 1 1 1 1 1 1 1
2 : 9 8 7 6 5 4 3 2 1
3 : ...
여기에서 K=3이라면 dp[3][0], 즉위 DP에서 2번째 행의 원소의 총 합이 원하는 결과이다. 이를 얻기위해 아래와 같이 코드를 작성하였다.
1번째 행부터 작성을 시작하기 때문에, sum에는 1을 미리 넣어주었다. nextSum에는 다음 행의 sum에 사용될 값이 들어간다. 위에서 작성한 것처럼 dp값 들의 관계를 통해 다른 dp값을 채우지 않고 sum을 사용한 이유는 모듈러연산(%)에 의해 음의 dp값이 나오지 않게 하기 위해서이다.
vector<vector<int>> dp(K, vector<int> (N+1, 0));
long sum = 1;
long nextSum;
for(int i = 1; i < K; i++) {
nextSum = 0;
for(int j = 0; j <= N; j++) {
dp[i][j] = sum % 1000000000;
sum -= dp[i-1][j];
nextSum += dp[i][j];
}
sum = nextSum;
}
cout << sum % 1000000000;코멘트
그건 그렇고, 내 휴대폰 전화번호부가 다 날라간 건 너무 가슴아프다 ㅜㅜㅜ 전화... 안하긴 하지만... ㅋㅋㅋ
코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
vector<vector<int>> dp(K, vector<int> (N+1, 0));
long sum = 1;
long nextSum;
for(int i = 1; i < K; i++) {
nextSum = 0;
for(int j = 0; j <= N; j++) {
dp[i][j] = sum % 1000000000;
sum -= dp[i-1][j];
nextSum += dp[i][j];
}
sum = nextSum;
}
cout << sum % 1000000000;
return 0;
}
Uploaded by Notion2Tistory v1.1.0