[백준 *Java] - 합분해 (2225)

 

합분해 문제 보기

2225번: 합분해

 

문제 설명
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다 (1+2와 2+1은 서로 다른 경우)
또한 한 개의 수를 여러번 쓸 수도 있다.

입력
첫째 줄에 두 정수 
N(1 <= N <= 200)
K(1 <= K <= 200) 이 주어집니다.

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

---

문제를 해석하면,

일단 예제입력 1을 기준으로

N이 20 

즉, 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 까지 있습니다

이 중에, K가 2이니깐,

수 2개를 뽑아서 

N인 20이라는 숫자를 만들 수 있는 경우의 수를 찾아야한다.

0+20,1+19,2+18,3+17,4+16,5+15,6+14,7+13,8+12,9+11,10+10

20+0,19+1,18+2,17+3,16+4,15+5,14+6,13+7,12+8,11+9,

총 21개 그래서 출력값은 21이 나와야합니다,

 

 

👇 실패한 내 로직 설계 

---

DP[201][201] 로 설정

K가 3일 때,

N이 1일 때, 0 1 : 001*3 = 3개

: DP[1][0] = 3

N이 2일 때, 0 1 2 => 002*3 011*3  = 6개

: DP[2][0] = 6

N이 3일 때, 0 1 2 3 => 003*3 012*6  111 = 10개

: DP[3][0] = 9 (+1)

N이 4일 때, 0 1 2 3 4 => 004*3 013*6 112*3 022*3    = 15개

: DP[4][0] = 12, DP[4][1]= 3

N이 5일 때, 0 1 2 3 4 5 => 005*3 014*6  023*6 122*3  113*3 = 18개

: DP[5][0] = 15, DP[5][1]= 6

N이 6일 때, 0 1 2 3 4 5 6 => 006*3 015*6 114*3  024*6  033*3 123*6   222 = 28개

: DP[6][0] = 18, DP[6][1]= 9 (+1)

---

N이 1일 때, 0 1 : 001*3 = 3개

: DP[3][1] = 3

N이 2일 때, 0 1 2 => 002*3 011*3  = 6개

: DP[3][2] = DP[3][1] + DP[3][0]

N이 3일 때, 0 1 2 3 => 003*3 012*6  111 = 10개

: DP[3][3] = DP[3][2] + DP[3][1]

N이 4일 때, 0 1 2 3 4 => 004*3 013*6 112*3 022*3    = 15개

: DP[3][4] = DP[3][3] + DP[3][2]

N이 5일 때, 0 1 2 3 4 5 => 005*3 014*6  023*6 122*3  113*3 = 21개

: DP[3][5] = DP[3][4] +  DP[3][2]

N이 6일 때, 0 1 2 3 4 5 6 => 006*3 015*6 114*3  024*6  033*3 123*6   222 = 28개

: DP[3][6] = DP[3][5] + DP[3][2] + 1

N이 7일 땐, DP[3][7] = DP[3][6] + DP[3][3]

> k의 배수일 때 +1개씩,

---

K가 2일 때,

N이 1일 때, 0 1 => 01*2 = 2개

: DP[1][0] = 2

N이 2일 때, 0 1 2 => 02*2 11 = 3개

: DP[2][0] = 2 +1

 

N이 3일 때, 0 1 2 3 => 03*2 12*2 = 4개

: DP[3][0] =  2, DP[3][1] = 2

N이 4일 때, 0 1 2 3 4 => 04*2 13*2 22 = 5개

: DP[4][0] = 2, DP[4][1] = 2  +1

 

N이 5일 때, 0 1 2 3 4 5 => 05*2 14*2 23*2 = 6개

: DP[5][0] = 2, DP[5][1] = 2, DP[5][2] = 2

N이 6일 때, 0 1 2 3 4 5 6 => 06*2 15*2 24*2 33 = 7개

: DP[6][0] = 2, DP[6][1] = 2, DP[6][2] = 2  +1

---

하.. 생각을 해보니, 

N에 대해서 합을 나열하고 규칙을 찾고있었다...

2차배열로 접근을 한다면,

N의 K가 1일때는?

       K가 2일때는?

       K가 3일때는?...... 의 식을 구했다면, 충분히 찾을 수 있는 문제였던 거 같다...

 

결과적으로 dp[N][K] = dp[N-1][K] + dp[N][K-1] 이라는 점화식을 구할 수 있다.

짧은 시간 내에 빠르게 규칙을 찾는 건 굉장히 힘든 작업인 거 같고 아직도 반복 숙달이 필요하다...

 

 

정리하자면,

점화식은 

dp[N][K] = dp[N-1][K] + dp[N][K-1] 이며,

그리고 이 점화식에 맞게 초기화를 할 수 있는 부분을 초기화를 해주어야합니다.

- K가 1일 경우에는 N 전체가 1이 됩니다.

- N이 1일 경우에는 K가 어떤수가 오든 1이 됩니다. 

아래는 성공한 코드입니다.

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

public class Main {

    static int [][] DP;
    static final int MOD = 1000000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // DP 초기화 후, 초기화값 세팅
        DP = new int[N+1][K+1];
        for (int i = 1; i <= N; i++) DP[i][1] = 1;
        // K(더해야하는 수)는 K가 1일 땐 무조건 1개입니다.
        // 1, 2, 3, 4, 5, 6.....
        for (int i = 1; i <= K; i++) DP[1][i] = i;
        // N이 1일 경우엔 1<=1 까지라, 무조건 1개입니다.
		// 0+1, 0+0+1, 0+0+0+1 ....
        
        // dp[N][K] = dp[N-1][K] + dp[N][K-1] 점화식
        for (int i = 2; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                DP[i][j] = ( DP[i][j-1] + DP[i-1][j] ) % MOD;
            }
        }
        System.out.println(DP[N][K]);
    }
}