합-분해
합-분해
백준 2225번 문제
https://www.acmicpc.net/problem/2225
2225번: 합분해
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
1. 문제
문제
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
예제 입력 1
20 2
예제 출력 1
21
예제 입력 2
6 4
예제 출력 2
84
2. 풀이
■풀이 방법
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하라..
문제를 처음 봤을 때 잘 이해가 되지 않았다.
이럴 때는 문제의 주어진 조건의 경곗값을 넣어서 직접 답을 구해보는 것이 좋다.
문제에서 조건은 (1 ≤ N ≤ 200), (1 ≤ K ≤ 200) 이므로 N과 K에 각각 1을 넣어본다.
그러면 우리가 구해야 할 답은 다음과 같다.
"0부터 1까지의 정수 1개를 더해서 그 합이 1이 되는 경우의 수"
정수 한 개(K = 1)로 1(N = 1)을 만드는 경우는 "1" 그 자체를 넣는 수 한 가지밖에 없다.
이제 N을 조금씩 늘려보자.
K = 1, N = 2이라면?
정수 한 개로 2를 만드는 경우도 "2" 하나밖에 없다.
즉, K = 1일 때 N = n일 경우 그 경우는 "n" 단 하나이다.
이제 K = 2일 때를 생각해보자.
K = 2, N = 1이라면?
정수 두 개로 1을 만드는 경우는 "0 + 1", "1 + 0" 두 가지이다.
K = 2, N = 2이라면?
첫 번째 자리에 올 수 있는 수는 "0", "1", "2"로 총 3가지이다.
따라서 정수 두 개로 2를 만드는 경우는 "0 + 2", "1 + 1", "2 + 0"으로 세 가지이다.
그런데 위의 경우를 뒤에서부터, 즉 두 번째 자리에서부터 생각해보자.
두번째 자리에 올 수 있는 수도 "0", "1", "2"로 총 3가지이다.
만약 두 번째 자리가 "1" 이 된다고 하자.
그러면 첫 번째 자리에 올 수 있는 값은 (2 - 1)로 "1"이 된다.
그런데 이것은 맨 처음에 했던 정수 한 개로 1을 만드는 경우와 같다.
즉 K = 2, N = 2일 경우의 답은 다음의 합과 같다.
정수 한개로 0을 만드는 경우 + 정수 한개로 1을 만드는 경우 + 정수 한개로 2를 만드는 경우
d[k][n]을 0부터 n까지의 정수 k개를 더해서 n을 만드는 경우의 수라고 한다면 다음과 같은 식이 성립한다.
[점화식]
d[k][n] = d[k - 1][0] + d[k - 1][1] + ... + d[k - 1][n]
K = 3, N = n일 때도 생각해보자.
세 번째 자리에 올 수 있는 수는 0부터 n까지이다.
세번째 자리에 0이 온다면
"? + ? + 0 = n"이 되는 경우의 수를 구해야 한다.
이는 정수 두 개로 n을 만드는 경우(d[2][n])와 같다.
세 번째 자리에 1이 온다면
"? + ? + 1 = n"이 되는 경우의 수를 구해야 한다.
이는 정수 두 개로 n - 1을 만드는 경우(d[2][n - 1])와 같다.
이런 식으로 세 번째 자리에 n이 온다면 이 경우의 수는 d[2][0]과 같을 것이다.
따라서 우리가 구하려는 0부터 n까지의 정수 세 개로 n을 만드는 방법의 수(d[3][n])는
d[2][0] + d[2][1] + ... + d[2][n] 으로 위의 점화식을 따른다.
또한 위의 점화식은 다음과 같이 바꿀 수 있다.
[점화식2]
d[k][n] = d[k][n - 1] + d[k - 1][n]
//d[k][n - 1] = d[k - 1][0] + d[k - 1][1] + ... + d[k - 1][n - 1] 이기 때문위의 점화식으로 d[k][n]을 구하면 된다.
■ 코드
□ 입력
[입력]
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
.
.
.
}입력받은 N과 K값으로 n과 k를 초기화한다.
□ 초기화
[초기화]
public static void main(String[] args) {
.
.
.
int[][] d = new int[k + 1][n + 1]; //[1]
Arrays.fill(d[1], 1); //[2]
for (int i = 1; i < k + 1; i++) { //[3]
d[i][0] = 1;
}
.
.
.
}● [1] : 입력받은 N과 K의 값으로 0부터 N까지의 정수 K개로 N을 만드는 경우의 수를 원소로 하는 배열 d를 생성한다.
d[n][k]가 실제 의미하는 값을 n과 k에 맞추기 위해 각 값에 1을 더해서 초기화해준다.
ex) d[n][k] = 0부터 n까지의 정수 k개로 n을 만드는 경우의 수
● [2] : 점화식 상 k = 0일 때와 n = 0일 때는 구할 수 없기 때문에 초기값을 설정해주어야 한다.
그런데 k = 0은 정수 0개로 합을 만드는 경우라는 의미로 이 경우를 1로 주면 안 되고 0으로 주면 의미가 없기 때문에 k=0일 경우
는 넘어가고 k = 1일 경우를 구해서 넣어준다.
앞에서 직접 해본 것처럼 k = 1일 때의 경우는 n이 어떤 정수든 1이다.
● [3] : n = 0은 0을 만드는 경우의 수로 이 경우는 자릿수가 몇 개 던 0만을 더해야 하기 때문에 항상 1이다.
□ 계산, 출력
[계산, 출력]
public static void main(String[] args) {
.
.
.
for (int i = 2; i < k + 1; i++) { //[1]
for (int j = 1; j < n + 1; j++) {
d[i][j] = d[i][j - 1] + d[i - 1][j];
d[i][j] %= 1000000000; //[2]
}
}
System.out.println(d[k][n] % 1000000000);
}
}● [1] : 점화식을 사용해서 모든 d[][] 값을 구한다.
● [2] : 문제에서 답을 1,000,000,000으로 나눈 나머지 값을 요구하기 때문에 구해진 각 값을 1,000,000,000으로 나눈 나머지 값으로 변경해준다.
■ 전체 코드
[전체 코드]
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int[][] d = new int[k + 1][n + 1];
Arrays.fill(d[1], 1);
for (int i = 1; i < k + 1; i++) {
d[i][0] = 1;
}
for (int i = 2; i < k + 1; i++) {
for (int j = 1; j < n + 1; j++) {
d[i][j] = d[i][j - 1] + d[i - 1][j];
d[i][j] %= 1000000000;
}
}
System.out.println(d[k][n] % 1000000000);
}
}