[백준/JAVA] 2225번: 합분해

📖 문제

2225번: 합분해

 

 

 

💡  풀이 방식

• DP

DP[K][N] : 숫자 K개를 사용해 N을 만들 수 있는 경우의 수

 

1. 초기화

숫자 K개로 0을 만드는 경우의 수는 항상 1개이다.

for(int i = 1 ; i <= K ; i++) {
    dp[i][0] = 1;
}

 

 

2. 점화식 찾기

표를 그리다 보면, 한 칸은 해당 칸의 위쪽 값과 왼쪽 값을 합한 값으로 채우는 규칙을 발견할 수 있다.

그렇기 떄문에 점화식이 아래와 같이 성립된다.

 

for(int i = 1 ; i <= K ; i++) {
    for(int j = 1 ; j <= N ; j++) {
    	dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
    }
}

 

 

 

 

🔺 코드

import java.io.*;
 
public class Main {
    static final int MOD = 1_000_000_000;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] str = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int K = Integer.parseInt(str[1]);
        
        long[][] dp = new long[201][201];
 
        // 초기화
        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-1][j] + dp[i][j-1]) % MOD;
            }
        }
        
        System.out.println(dp[K][N]);
    }
}
 

 

 

➕ 다른 풀이 방식

내가 원래 풀려고 했던 방식!

[JAVA] 백준 2225번 : 합분해

 

점화식을 dp[N][K]로 잡아서 풀었었다. (dp[N][K] : K개로 N 만드는 경우의 수)
1%에서 틀려서 뭐지,,,했는데 범위를 잘못 잡아서 그랬던 것이었다..

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MOD = 1_000_000_000;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] str = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int K = Integer.parseInt(str[1]);
        
        int[][] dp = new int[201][201];
        
        for(int i = 1 ; i <= 200 ; i++) {
            dp[i][1] = 1;
            dp[1][i] = i;
        }
        
        for(int i = 2 ; i <= N ; i++) {
            for(int j = 2 ; j <= K ; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
            }
        }
        
        System.out.println(dp[N][K]);
    }
}
 

 

---

💦 어려웠던 점

- 범위를 잘못잡아서 정답이 안 나왔던 것이었다,,,

 

 

🧐 새로 알게 된 내용

- 범위를 잘 잡자,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[JAVA] 백준 2225번 : 합분해

백준 2225 자바 - 합분해 (BOJ 2225 JAVA)