BOJ) 합분해

합분해

2225번: 합분해

풀이

 

0~ N까지의 정수 K 개를 선택하여 N을 만드는 경우의 수를 구하는 문제다.

덧셈의 순서가 다르면 다른 경우로 체크한다. (1 + 2 와 2 + 1 은 다른 경우)

각각의 수는 여러번 이용 가능하며, 1,000,000,000으로 나눈 나머지를 출력해야한다.

 

우선 k개를 이용했을 때, 특정 숫자 n을 구할 수 있는 경우의 수를 담기 위해 2차원 배열의 dp를 선언했다.

int[][] dp = new int[k][n];

우선 k = 1 일 때, (0 ~ N까지 하나만 이용했을 때) 숫자를 만들 수 있는 경우를 1로 저장해줬다.

(0이든, 1이든 ... N이든 자기 자신을 딱 하나 이용했을 때만 가능하기 때문에)

 

이후에 탐색을 하면서

dp[k][n] = ( dp[k][n] + dp[k-1][n-n이전 수] ) % MOD 라는 식을 통해 값을 저장해줬다.

위의 식은, 현재보다 하나 적은 갯수를 이용한 수 들 중, n을 만들 수 있는 갯수를 더 해주는 과정이다.

 

탐색 중인 k =2, n = 5라면

k=1만 이용했을 때, 0~5까지 만들 수 있는 경우에  k=2 , n =5를 만들 수 있는 조합을 만들어 주는 것이다.

k[1][0] + k[1][5] = k[2][5]가 되는 것이다.

 

이후 마지막에 저장된 dp[k][n]을 출력하면서 답을 구해줬다.

 

 

코드

 

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

public class Main {
    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());
        br.close();
        solution(n,k);
    }

    private static void solution(int n, int k) {
        int[][] dp = new int[k+1][n+1];
        final int MOD = 1000000000;

        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=j; l>=0; l--) { dp[i][j] = (dp[i][j] + dp[i-1][j-l]) %MOD; }
            }
        }
        System.out.println(dp[k][n]);
    }
}