[백준 java] 2225번 합분해 DP

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

2225번: 합분해

 

 

[문제 풀이]

arr[a][b] -> a개의 숫자를 이용해서 b를 만들수 있는 경우의 수

1개의 숫자를 이용해서 b를 만들수 있는 경우는 무조건 1개 임으로 1로 초기화 한다.

arr[a][b]=arr[a-1][b]+arr[a][b-1]

arr[3][2] = 002,020,200,110,101,011 (6)

arr[4][1] = 0001,0010,0100,1000 (4)

arr[4][2] = 0002,0020,0200, 0110,0101,0011,1001,1010,1100, 2000 (10)        

arr[3][2]의 앞에 0을 붙이는 경우 + arr[4][1]의 제일 앞자리에 1을 더하는 경우 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static final int mod=1000000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int arr[][] = new int[k][n + 1];
        Arrays.fill(arr[0], 1);

        for (int i = 1; i < k; i++) {
            arr[i][0] = 1;
            for (int j = 1; j <= n; j++) {
                arr[i][j] = (arr[i - 1][j] + arr[i][j - 1])%mod;
            }
        }
        System.out.println(arr[k - 1][n]%mod);
    }
}