DP - 2225(합분해)

2225번: 합분해 (acmicpc.net)

2225번: 합분해

 

합분해 문제입니다. 우선 합분해를 구하기 위해서 이중배열을 선언해주었습니다. 이유는 Bottom-up방식을 통해서 값을 하나씩 갱신해 나갈것인데 이를 위해서 N의 합인 수와 K개의 정수인 경우의수를 각각 나누어주어야 하기 때문입니다. 

따라서 다음과 같은 코드를 작성했습니다. 

 

 

package com.company;

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


public class Main {



    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        long dp[][] = new long[k+1][n+1];

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

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

 

 

부족했던 점

 

2차원 배열을 선언해야 한다는 점까지는 생각했지만 값을 갱신하는 방법 특히, 삼중 반복문을 사용하는 부분에서 어려움을 겪었습니다.