BJ_G5_2225_합분해 - Java

[문제링크]

https://www.acmicpc.net/problem/2225

2225번: 합분해

---

[문제]

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

 

---

[설명]

이 문제는 DP 문제이다.

이차원 DP 문제로 dp[1][1]부터 하나씩 해보니 생각보다 쉽게 풀렸다.

K=1일 경우 모든 경우는 1가지 이기 때문에 1을 넣어준다.

	N=1	N=2	N=3	N=4
K=1	1	1	1	1
K=2	2	3	4	5
K=3	3	6	10	15
K=4	4	10	20	35

이런식으로 되기 때문에 dp[i][j] = dp[i][j-1] + dp[i-1][j] 가 나오게 된다.

 

 

백준 알고리즘 2225번 JAVA풀이

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scann = new Scanner(System.in);
		int N=scann.nextInt();
		int K=scann.nextInt();
		long[][] dp = new long[K+1][N+1];
		for(int i=1;i<=K;i++) {
			dp[i][0]=1;
		}
		for(int i=1;i<=K;i++) {
			for(int j=1;j<=N;j++) {
				dp[i][j]=(dp[i][j-1]+dp[i-1][j])%1000000000;
			}
		}
		System.out.println(dp[K][N]);
	}
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.