[JAVA]백준 2225번: 합분해

www.acmicpc.net/problem/2225

2225번: 합분해

 

1. 문제 설명

 

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 세는 문제이다.

 

Top down 방식과 Bottom up 두 가지 방식으로 풀 수 있다.

 

1) Top down

 

변수 remain을 남은 합, k_use를 현재까지 더한 정수의 개수라고 한다면

 

cache [remain][k_use]=cache [remain-1][k_use]+cache [remain][k_use-1]이다.

 

 

점화식을 이용하여 위의 식을 얻을 수 있다.

 

cache [remain][k_use]= ∑cache [remain-x][k_use-1] (0 <=x <=remain)

cache [remain-1][k_use]=∑cache [remain-1-x][k_use-1] (0 <=x <=remain-1)

 

따라서 cache [remain][k_use]=cache [remain-1][k_use]+cache [remain][k_use-1]이 된다.

 

2) Bottom up

 

변수 x를 현재까지의 합, y를 현재까지 사용한 정수의 개수라고 한다면

 

cache [x][y]=cache [x][y-1]+cache [x-1][y]이다. (위의 식과 증명 방법은 같다.)

 

3) 나머지 연산

 

이 문제는 답을 1,000,000,000을 나눈 나머지를 출력해야 한다.

 

따라서 cache 배열에 값을 저장할 때

 

임의의 수 A를 cache [x][y]에 더할 때 아래와 같은 연산을 수행하였다.

 

cache [x][y]=(cache [x][y]+A)% mod

 

4) 시간 복잡도

 

O(nk)

 

2. 코드

 

1) Top down

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int n;
    public static int k;
    public static int mod=1000000000;


    public static int[][] cache=new int[202][202];

    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);

        n = scan.nextInt();

        k = scan.nextInt();



        for (int x = 0; x <= 200; x++)
            for (int y = 0; y <= 200; y++) {
                cache[x][y] = -1;
            }


        System.out.println(make(n, k));


        scan.close();


    }

    public static int make(int remain, int k_use){

        if(k_use==0){
            if(remain==0)
                return 1;
            else
                return 0;
        }

        if(remain<0)
            return 0;

        if(cache[remain][k_use]!=-1)
            return cache[remain][k_use];


        cache[remain][k_use]=(make(remain-1,k_use)+make(remain,k_use-1))%mod;

        return cache[remain][k_use];


    }


}

 

2) Bottom up

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int n;
    public static int k;
    public static int mod=1000000000;


    public static int[][] cache=new int[202][202];

    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);

        n = scan.nextInt();

        k = scan.nextInt();


        for (int x = 0; x <= 200; x++)
            for (int y = 0; y <= 200; y++) {

                if(x==0 || y==1)
                    cache[x][y] = 1;
                else
                    cache[x][y] = 0;
            }






        for(int x=1;x<=n;x++){
            for(int y=2;y<=k;y++){
                cache[x][y]=(cache[x][y-1]+cache[x-1][y])%mod;
            }

        }




        System.out.println(cache[n][k]);

        scan.close();


    }







}

 

백준 제출

윗 제출이 Top down, 아래 제출이 Bottom Up 제출의 결과이다.