[백준][2225번] 합분해

문제 URL

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

나의 풀이

package backjoon;

import java.util.Scanner;

public class Main {
    public static int[] d;
    public static final int mod = 1000000000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        //d[i] = O부터 n까지 더 해서 합이 i가 되는 경우의 수
        d = new int[n + 1];

        for (int i = 0; i <= n; i++)
            d[i] = 1;

        //2번 더하는경우 부터 k번째 더하는 경우까지 순차적으로
        for (int i = 2; i <= k; i++) {
            //뒷요소부터 계산한다. k-1번째 더 해진 앞요소들을 탐색해야하기때문.
            for (int j = n; j >= 1; j--) {
                for (int a = 0; a < j; a++) {
                    d[j] += d[a];
                    d[j] %= mod;
                }
            }
        }

        System.out.println(d[n]);
    }
}

다른 풀이 **

import java.util.*;
import java.math.*;

public class Main {
    public static long mod = 1000000000L;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long[][] d = new long[k+1][n+1];
        d[0][0] = 1;
        for (int i=1; i<=k; i++) {
            for (int j=0; j<=n; j++) {
                for (int l=0; l<=j; l++) {
                    d[i][j] += d[i-1][j-l];
                    d[i][j] %= mod;
                }
            }
        }
        System.out.println(d[k][n]);
    }
}

느낀점

동적계획법 을 이용한 문제다.

내가한것 보다 괜찮은 다른풀이를 보았다. 2차원배열을 활용하는 것이다.

백준강의 say, 난이도가 낮을수록 문제에서 구해야하는 것을 점화식으로 그대로 옮기 완성되는 경우가 많다. ex) D[K][N] = 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수

• 시간복잡도 : O(KN제곱)