[백준알고리즘] dp - 2225번 합분해 문제

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

2225번: 합분해

이것도 동적계획법 문제인데 뾰족한 수가 떠오르질 않는다.

0부터 N까지의 수들 중 K개를 더하여 N이 되는 경우들을 구하는 문제인데..

머리아파서 결국 못풀고 찾아봤다

방법을 찾아보니 점화식이 나온다. 어째서 그런 식이 세워진다는 건지 이해가 안가다가

표를 보며 고민해보니 좀 이해가 간다..

표를 보면 이런 규칙이 보인다

k개의 수들을 더하여 N을 만들 수 있는 경우의 수를 알기 위해서는

k-1수들을 더하여 N-0을 만들 수 있는 경우의 수,

k-1 수들을 더하여 N-1을 만들 수 있는 경우의 수,

...

k-1 수들을 더하여 N-N(0이되겠지)을 만들 수 있는 경우의 수

이들의 합이 된다!

 

k-1개의 수들을 더하여 N-0을 만들 수 있는 경우의 수도 마찬가지로

(k-1)-1개의 수들을 더하여 (N-0)-0을 만들 수 있는 경우의 수,

(k-1)-1개의 수들을 더하여 (N-0)-1을 만들 수 있는 경우의 수,

...

(k-1)-1개의 수들을 더하여 (N-0)-N을 만들 수 있는 경우의 수

이들의 합이 된다

표를 앞에서부터 채워 나가면 뒤에 있는 해답도 구할 수 있는 식이다

이런걸 bottom-up 방식이라고 하는게 맞나요?

 

정리하자면 dp[k][n]을 구하기 위해 dp[k-1][n-n]...dp[k-1][n-0]의 값들을 더하면 된다

이때 dp[k-1][n-n]에서 dp[k-1][n-1]까지의 값의 합은

dp[k][n-1]의 값과 동일하다

그러니까 dp[k][n-1]에다가 dp[k-1][n] 이 두개 값을 알면 알고자 하는 dp[k][n]의 값을 구할 수 있음

(dp[k][n-1]는 바로 왼쪽에 있는 값이고 dp[k-1][n]는 바로 위에 있는 값이다)

 

내 설명보다는

https://computer-choco.tistory.com/545

[알고리즘 문제 풀이][DP] 백준 2225번 - 합분해

이 블로그 글을 추천합니다

 

이제 이걸 코드로 구현해보았다

코드는 그래도 간단한편..?물론 풀이요령을 찾아보지 않고 풀었다면 엄청 막막했겠지만..

package week1;

import java.io.*;
import java.util.StringTokenizer;

public class Bj2225 {   //백준 2225번 합분해 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());   //0~N까지의 정수 이용, 합이 N이 되도록
        int K = Integer.parseInt(st.nextToken());   //k개의 정수를 이용하여 N을 구한다

        int[][] dp = new int[K][N+1]; //KxN+1 크기의 2차원 배열을 만든다(N은 0부터 시작이므로 +1한 크기로 한다)

        for (int k = 1; k <= K; k++) {  //1~k까지(실제 배열의 인덱스는 0부터 시작이므로 k-1라고 매번 해줬다)
            for (int n = 0; n <= N; n++) {  //n은 0~n까지
                if(k == 1) dp[0][n] = 1;
                else if(n==0) dp[k-1][n] = 1;
                /*맨 첫줄은 다 1이 들어간다.k가 한개라면 N이 뭐든간에 한가지 경우밖에 없으니까
                 여기서 시작해 나머지들도 구할수있음
                 N이 0인 경우 또한 K가 뭐든간에 한가지 경우뿐이다
                 */
                else{
                    dp[k-1][n] = dp[k-1][n - 1] + dp[k - 2][n]; //왼쪽에 있는 dp값 + 위에 있는 dp값
                }

            }
        }

        bw.write(Integer.toString(dp[K-1][N] % 1000000000));    //나머지 출력
        bw.flush();
        bw.close();
    }
}

 

이렇게 했더니 단박에 틀렸습니다가 떴다. ㅡㅡ

나머지 연산을 for문 내에서 바로바로 해줘야 하나 싶어서 바꿨지만 여전히 틀렸다.

반례를 더 찾아봐도 결과 제대로 나오는것 같은데 뭐가 문제지.....?

아...

일단 for문 내에서 나머지 연산을 하도록 하는건 맞는것같다(이렇게 하면 int->long 굳이 안바꿔도 되는듯..?)

그 다음 문제는 내가 숫자를 잘못쓴거였다..ㅋㅋㅋㅋ

십억, 즉 1000000000에서 0을 하나 빼먹었었음

정신 차리자.~~

 

수정 코드

package week1;

import java.io.*;
import java.util.StringTokenizer;

public class Bj2225 {   //백준 2225번 합분해 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());   //0~N까지의 정수 이용, 합이 N이 되도록
        int K = Integer.parseInt(st.nextToken());   //k개의 정수를 이용하여 N을 구한다

        int[][] dp = new int[K][N+1]; //KxN+1 크기의 2차원 배열을 만든다(N은 0부터 시작이므로 +1한 크기로 한다)

        for (int k = 1; k <= K; k++) {  //1~k까지(실제 배열의 인덱스는 0부터 시작이므로 k-1라고 매번 해줬다)
            for (int n = 0; n <= N; n++) {  //n은 0~n까지
                if(k == 1) dp[0][n] = 1;
                else if(n==0) dp[k-1][n] = 1;
                /*맨 첫줄은 다 1이 들어간다.k가 한개라면 N이 뭐든간에 한가지 경우밖에 없으니까
                 여기서 시작해 나머지들도 구할수있음
                 N이 0인 경우 또한 K가 뭐든간에 한가지 경우뿐이다
                 */
                else{
                    dp[k-1][n] = dp[k-1][n - 1] + dp[k - 2][n]; //왼쪽에 있는 dp값 + 위에 있는 dp값
                    dp[k-1][n] %= 1000000000;    //미리 여기서 나머지 연산을 해준다
                }

            }
        }

        bw.write(Integer.toString(dp[K-1][N]));    //나머지 출력
        bw.flush();
        bw.close();
    }
}