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

2225 합분해

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

2225번: 합분해

 

 

 

 

---

백준 2225번 문제 합분해

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://yeoeun-ji.tistory.com/49

참고 블로그

https://hu-coding.tistory.com/28

n, k의 순서가 반대긴 하지만 계산 접근에 유용했던 블로그

 

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

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
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());
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] dp = new int[n+1][k+1];
        final int MOD = 1_000_000_000;
        
        // k=1 -> [1][1] = 1, [2][1] = 2, ... 무조건 1개씩
        for(int i = 1; i < n+1; i++) {
            dp[i][1] = 1;
        }
        
        // n=1 -> [1][1] = 1, [1][2] = 0+1,1+0, [1][3] = 1+0+0, 0+1+0, 0+0+1, ... k개씩
        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++) {
                // 오버 플로우 방지를 위해 MOD의 나머지로 구한다
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
            }
        }
        System.out.println(dp[n][k]);
    }
 
}
 

 

모든 dp 문제가 그렇듯 점화식을 찾는 게 가장 중요하다

 

 

---