[BOJ]2225번: 합분해(java)

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

2225번: 합분해

 

2225번: 합분해(c++) 에 그림 설명 추가

 

방법 1: Top-down

import java.util.Scanner;
 
public class Main {
 
    static int[][] arrCount;
 
    public static void main(String[] args) {
        try {
            Scanner sc = new Scanner(System.in);
            int iNum = sc.nextInt();
            int iCount = sc.nextInt();
 
            arrCount = new int[iNum + 1][iCount + 1];
 
            calculate(iCount);
 
            System.out.println(arrCount[iNum][iCount] % 1000000000);
 
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
 
    public static void calculate(int c) {
 
        if (c == 0) {
            return;
        }
        calculate(c - 1);
        
        arrCount[0][c] = 1;
        
        for (int n = 1; n < arrCount.length; n++) {
            arrCount[n][c] = (arrCount[n - 1][c] + arrCount[n][c - 1]) % 1000000000;
        }
    }
}

 

방법 2: Bottom-up

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        try {
            Scanner sc = new Scanner(System.in);
 
            int iNum = sc.nextInt();
            int iCount = sc.nextInt();
            int[][] arrCount = new int[iNum + 1][iCount + 1];
 
            for (int c = 1; c <= iCount; c++) {
 
                arrCount[0][c] = 1;
 
                for (int n = 1; n <= iNum; n++) {
                    arrCount[n][c] = (arrCount[n - 1][c] + arrCount[n][c - 1]) % 1000000000 ;
                }
            }
 
            System.out.println(arrCount[iNum][iCount] % 1000000000);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

바텀업과 탑다운 속도가 같았음

 

 

TIP1

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

 

주어진 수 N을 K가지 수로 표현하는 방법의 수를 D[N, K]라고 하자. 

 

N=3, K=3 인 경우를 예로 들자.

 

D[3, 3] = (3을 더할 때) + D[0, 2]

              (2을 더할 때) + D[1, 2]

              (1을 더할 때) + D[2, 2]

              (0을 더할 때) + D[3, 2]

 

 

이때, D[0, 2] ~ D[3, 2] 는

D[0, 2] = (0을 더할 때) + D[0, 1]

               = 1

(N을 1자리수로 표현하는 방법 = 1 이므로)

D[1, 2] = (1을 더할 때) + D[0, 1]

              (0을 더할 때) + D[1, 1]

               = 2

D[2, 2] = (2을 더할 때) + D[0, 1]

               (1을 더할 때) + D[1, 1]

               (0을 더할 때) +D[2, 1]

               = 3

D[3, 2] = (3을 더할 때) + D[0, 1]

               (2을 더할 때) + D[1, 1]

               (1을 더할 때) + D[2, 1]

              (0을 더할 때) + D[3, 1]

               = 4

 

 

색으로 중복되는 부분을 표시했다

다시 D[3, 3]로 돌아가면 

 

D[0, 3] = (0을 더할 때) + D[0, 2]

D[1, 3] = (1을 더할 때) + D[0, 2]

              (0을 더할 때) + D[1, 2]

D[2, 3] = (2을 더할 때) + D[0, 2]

               (1을 더할 때) + D[1, 2]

               (0을 더할 때) + D[2, 2]

D[3, 3] = (3을 더할 때) + D[0, 2]

               (2을 더할 때) + D[1, 2]

               (1을 더할 때) + D[2, 2]

               (0을 더할 때) + D[3, 2]

 

여기서 D[N, K] = D[N - 1, K] + D[N, K - 1] 임을 알 수 있다!

 

실제 수를 대입해서 문제를 풀어나가보자.