[백준(baekjoon) 2225] 합분해

문제

백준 2225

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하시오

• 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우).
• 한 개의 수를 여러 번 쓸 수도 있다.

해결

결론부터 말하자면 다음과 같은 규칙이다.

• n = 1 : dp[n][k] = k;
• k = 1 : dp[n][k] = 1;
• else : dp[n][k] = dp[n - 1][k] + dp[n][k - 1];

어떻게?

n = 2, k = 3일 경우를 보자.

• dp[n - 1][k]의 각 케이스 마지막 숫자에 + 1을 해주면 k개의 숫자를 활용해 n을 만들 수 있다.
• dp[n][k - 1]의 각 케이스에 + 0을 해주면 k개의 숫자를 활용해 n을 만들 수 있다.

알고리즘

DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

공통적인 것

• answer에 값들을 저장한다는 것
  
  • n < 11이고 수가 작아 아예 11로 크기를 정의하고 접근하기 쉽게 index = 1부터 시작하였다.

1. Top-Down 방식

1.import java.util.*;
2.
3.public class Main {
4.    static int[][] dp;
5.    public static void main(String[] args) {
6.        Scanner sc = new Scanner(System.in);
7.        int n = sc.nextInt();
8.        int k = sc.nextInt();
9.
10.        dp = new int[n + 1][k + 1];
11.        System.out.println(goTo(n, k));
12.    }
13.
14.    static int goTo (int n, int k) {
15.        if (n == 1)
16.            dp[n][k] = k;
17.        else if (k == 1)
18.            dp[n][k] = 1;
19.        else if (dp[n][k] == 0)
20.            dp[n][k] = goTo(n - 1, k) + goTo(n, k - 1);
21.       return dp[n][k] % 1000000000;
22.    }
23.}

2. Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    static int[] answer = new int[11];
5.    public static void main (String[] args) {
6.        Scanner sc = new Scanner(System.in);
7.        int T = sc.nextInt();
8.
9.        for (int i = 1; i <= 10; i++) {
10.            if (i < 4) answer[i] = 1;
11.            for (int j = 1; j <= 3 && j < i; j++) {
12.                answer[i] += answer[i - j];
13.            }
14.        }
15.
16.        for (int i = 0; i < T; i++) {
17.            int n = sc.nextInt();
18.            System.out.println(answer[n]);
19.        }
20.    }
21.}

결과

1. Top-Down 방식
2. Bottom-Up 방식