[DP][Java][BOJ] #2225. 합분해

#DP  #Gold5

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으로 나눈 나머지를 출력한다.

입출력 예

입력	출력
20 2	21
6 4	84

 

💡 해결 포인트

1. K개의 숫자로 N을 만드는 방법은, (K-1)개의 숫자로 어떤 수를 만든 뒤, 하나를 추가
- 예를 들어, N=3, K=2인경우(숫자 2개로 3을 만드는 방법)
- 마지막 숫자가 어떤거였는지 알아보는 것!

(1) 마지막 숫자가 0인 경우 
- K=1일 때 N=3을 만든 것과 같음
- 따라서 3

(2) 마지막 숫자가 1인 경우
- K=1일 때 N=2를 만든 것과 같음
- 따라서 2

(3) 마지막 숫자가 2인 경우
- K=1일 때, N=1을 만든 것과 같음
- 따라서 1

(4) 마지막 숫자가 3인 경우
- K=1일 때, N=0을 만든 것과 같음
- 따라서 0


이렇게 4가지 방법이 있다.
dp[2][3]=dp[1][3]+dp[1][2]+dp[1][1]+dp[1][0]

 

 

 

🌷 내 코드

1.

import java.io.*;
import java.util.*;

public class BOJ_2225 {
  public static void main(String[] args) throws IOException {
    System.setIn(new FileInputStream("example.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String[] line = br.readLine().split(" ");
    int N = Integer.parseInt(line[0]); 
    int K = Integer.parseInt(line[1]);

    int[][] dp = new int[K + 1][N + 1]; // dp[K][N]: 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수

    // 예외 처리ㅇ
    for (int i = 0; i <= N; i++) {
      dp[1][i] = 1;
    }

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

    System.out.println(dp[K][N]);
  }
}

 

🌷 코멘트

나 그냥 DP는 포기할래.. 그냥 코드를 하나하나 열심히 읽었다...

백준 문제는 일단 독해력이 베이스가 되어 있어야 하는 것 같다. 문제를 자꾸 다르게 읽어서 아예 이해가 안되어버림. 근데 나 문관데? 이렇게 오늘도 또 긁히는 나 

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com