백준 2225번 합분해(자바) 풀이 - DP

합분해

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

25474

10987

7927

41.579%

문제

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

---

이 문제는 규칙 찾는데는 어렵지 않았지만 for문을 작성하는데 많이 헷갈렸다..

풀이 :

일단 맨 앞에 숫자를 하나 고정시킨다고 생각하면 쉽다.

예를 들어 0부터 5까지 정수 3개를 더해 5를 만드는 예시를 생각해보자.

그럼 일단 맨 앞에 0 부터 5까지의 숫자를 위치시킨다. 그 후 생각을 해보면 다음과 같다.

0 + (0부터 5까지 정수 2개를 더해 5를 만들기)

1 + (0부터 5까지 정수 2개를 더해 4를 만들기)

2 + 0부터 5까지 정수 2개를 더해 3을 만들기

3 + 0부터 5까지 정수 2개를 더해 2를 만들기

4 + 0부터 5까지 정수 2개를 더해 1을 만들기

5 + 0부터 5까지 정수 2개를 더해 0을 만들기

 

즉, dp[5][3] = dp[5][2]+dp[4][2]+dp[3][2]+dp[2][2]+dp[1][2]+dp[0][2] 이다.

이 문제에서도 주의할 점은 dp배열을 long 배열로 만들어줘야 한다는 것이다!!

---

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        long[][] dp = new long[n+1][k+1];
        for (int i = 0; i <= n; i++) {
            dp[i][1] = 1;
        }

        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                for (int m = 0; m <= j; m++) {
                    dp[j][i] += dp[m][i-1] % 1000000000;
                }
            }
        }

        System.out.println(dp[n][k]%1000000000);

    }
}