백준 2225번 합분해 Java (☆공부 272일차)

2225 합분해

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

2225번: 합분해

 

 

 

 

---

백준 2225번 문제 합분해

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	39070	17442	12787	43.105%

문제

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

힌트

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/258

공부 132일차: 백준 2225번 합분해 자바 java

4달 전에 푼 문제

 

2차원 배열을 이용한다

dp[n][k]

 

k가 1이면dp[n][1] = 1 로 고정된다(n이 1이면 1만, 2면 2만, ...)

 

n이 1이면dp[1][k] = k 로 고정된다([1][1] = 1, [1][2] = 0+1,1+0, [1][3] = 1+0+0, 0+1+0, 0+0+1, ... k개씩)

 

최종 점화식: dp[n][k] = dp[n-1][k] + dp[n][k-1]

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        final int MOD = 1_000_000_000;
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] dp = new int[n+1][k+1];
        
        for(int i = 1; i < n+1; i++) {
            dp[i][1] = 1;
        }
        
        for(int i = 1; i < k+1; i++) {
            dp[1][i] = i;
        }
        
        for(int i = 2; i < n+1; i++) {
            for(int j = 2; j < k+1; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
            }
        }
        
        System.out.println(dp[n][k]);
    }
 
}
 

 

 

 

---