👓 문제 설명
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
💣 제한 사항
- 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
- 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
🚨 접근 방법
0부터 N까지의 숫자 (N+1)개의 숫자 중
K를 뽑아 그 합이 N이 되는 경우의 수를 구하는 문제이다.
입력이 3 2인 경우는
{1,2,3}의 숫자가 있을 때
2개를 뽑아(중복 허용) 그 합이 3인 경우를 뜻한다.
이를 만족하는 경우의 수는 다음과 같이 총 4가지 경우다.
(3,0) (0,3)
(2,1) (1,2)
작은 값을 구하는 경우의 수가
큰 값을 구하는 경우의 수에 적용되는 것을 파악하기 위해
식을 직접 써보았다.
dp[1][0] = 0
dp[1][1] = 1
dp[1][2] = 10, 01 : 2
dp[1][3] = 100 010 001 : 3
dp[1][4] = 1000 0100 0010 0001 : 4
... dp[1][n] = n
dp[2][0] = 0
dp[2][1] = 2 : 1
dp[2][2] = 11, 20, 02 : 3
dp[2][3] = 110, 101, 011 200, 020, 002 : 6
dp[2][4] = 1100, 1010, 0110, 2000, 0200, 0020, 1001, 0011, 0101, 0002 : 10
dp[3][0] = 0
dp[3][1] = 3 : 1
dp[3][2] = 12, 21, 30, 03 : 4
dp[3][3] = 300, 030, 003, 210, 201, 102, 120, 012, 021, 111 : 10
(a는 만드려는 수, b는 사용한 숫자의 개수)
직감적으로 보면
dp[a][b] = dp[a][b-1] + dp[a-1][b]를 알 수 있다.
그렇다면 이를 검증해보자.
dp[3][2]의 경우
(1,2) (2,1) (3,0) (0,3)이다.
dp[3][1]의 경우
(3)이다.
dp[2][2]의 경우
(1,1) (2,0) (0,2)이다.
dp[3][1]은 이미 만드려는 수를 충족했다.
숫자를 1개만 더 사용하면 되므로 숫자 0을 추가하면 된다. (3) -> (3,0)
dp[2][2]의 경우 이미 고른 숫자에 1을 더하면 된다.
(1, 1+1), (2, 0+1), (0, 2+1)
-> (1,2), (2,1), (0,3)
문제에서 중복을 허용한다. (1+2, 2+1은 다르다)라고 적혀있었다.
dp[2][2]에서 1을 더한 결과를 보면
(1,2) (2,1)이 있는데 이 둘은 앞에 1을 더해도 같은 결과가 나온다.
🚈 풀이
#include<iostream>
#include<algorithm>
#define modnum 1000000000
using namespace std;
int n, m;
int dp[201][201];
int ans;
void func() {
for (int i = 1; i <= m; i++) {
dp[0][i] = i;
dp[1][i] = i;
dp[i][1] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = ((dp[i][j - 1] % modnum) + (dp[i - 1][j] % modnum)) % modnum;
}
}
ans = dp[n][m];
cout << ans;
}
int main() {
cin >> n >> m;
func();
return 0;
}