합분해 [JAVA] (백준 2225)

 

문제

문제 링크 : https://www.acmicpc.net/problem/2225

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128MB	21456	9304	6697	41.938%

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

풀이

일단 직관적으로 알아낼 수 있는 정보들은 다음과 같다.

1. K가 1인 경우, 모든 답은 1이다. (자기자신)
2. 0을 더해야 하는 경우는 (실제로 N >0이지만, N+0의 경우를 더해야 하므로) 무조건 1이다.

그렇다면 직접 숫자를 통해 생각해보자

2 ,2 -> 2 + 0 / 1 + 1 / 0 + 2 -> 3가지

= 2,1 + 1,1 + 0,1

이를 통해 생각할 수 있는 풀이식은 결국 다음과 같다.

$A_{kn} = \sum_iA_{k-1n-i}$

그렇다면 K와 N을 행/열로 두고 이차원 배열을 생성한 뒤 문제를 바꿔 생각하면

$ A[K][N] = \sum_i(A[K-1][N-i])$이라 할 수 있다.

범위는 N = 0~N, K = 1~K 이고, 이에 따라서 재귀식을 구현한다면 문제를 해결할 수 있다.

 

코드

import java.io.IOException;

public class Main {

    static int N;
    static int K;
    static long[][] cacheN;

    public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{

        String[] spl = br.readLine().split(" ");

        //숫자 0~N
        N = Integer.parseInt(spl[0]);        
        //합 1~K
        K = Integer.parseInt(spl[1]);

        cacheN = new long[K+1][N+1];    

        //라인 초기화
        for(int i=0; i<N+1; i++) {
            cacheN[1][i] = 1;
        }
        for(int i=1; i<K+1; i++) {
            cacheN[i][0] = 1;
        }

        //풀이
        GetCache(K, N);

        //정답
        System.out.println(cacheN[K][N]);
    }

    public static long GetCache(int k, int n) {
        if(cacheN[k][n] != 0) {
            return cacheN[k][n] ;
        }

        for(int i=0; i<=n; i++) {
            cacheN[k][n] = (cacheN[k][n] +  GetCache(k-1, n-i))% 1000000000;
        }
        return cacheN[k][n];
    }
}

 

결과

 

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!