[백준] code.plus(다이나믹 프로그램 part 1,JAVA)2225번, 합분해

문제 링크

2225번: 합분해

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

다이나믹 프로그램

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

 

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 0~N까지의 수 중 K번을 더해서 N이 되는 경우의 수를 출력해야 한다.

2. 0~N까지의 수는 중복되어 사용이 가능하다.

3. 결과를 출력할 때 1,000,000,000을 나눈 나머지를 출력한다.

 

배열

 

DP : 메모이제이션 배열

 

DP 배열을 이용하여 0~N의 수를 K번 더할 때 N이 되는 경우의 수를 구하였습니다.

 

DP[i][j]는 i의 값이 0~N의 수에서 j번을 사용하여 나올 수 있는 경우의 수를 저장하였습니다.

 

이 문제에서 만약 입력값이 N = 3, K = 3일 때 경우의 수는

 

3 = 0(2번 더하여 0이 나오는 경우의 수) + 3

3 = 1(2번 더하여 1이 나오는 경우의 수) + 2

3 = 2(2번 더하여 2가 나오는 경우의 수) + 1

3 = 3(2번 더하여 2가 나오는 경우의 수) + 0

 

위 경우의 수를 모두 더하는 것을 DP의 형태로 나타내면

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

 

DP[i][j] = DP[0][j-1] + DP[1][j-1] + .....  + DP[i][j-1]라는 식을 얻을 수 있습니다.

 

N = 3, K = 3일 때의 DP[][]배열을 표로 표현하면

 

	0	1	2	3
0	0	1	1	1
1	0	1	2	3
2	0	1	3	6
3	0	1	4	10

 

위에 표에서 값을 살펴보면

 

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

 

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

 

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

DP[2][3]에서 DP[0][2] + DP[1][2] = DP[1][3]으로 바꿀 수 있습니다.

DP[2][3] = DP[1][3] + DP[2][2] = 3 + 3 = 6의 형태로 바꿀 수 있습니다.

 

위와 같은 형태로 변경하여 값을 구하면 규칙을 얻을 수 있습니다.DP[i][j] = DP[i][j-1] + DP[i-1][j]로 구할 수 있습니다.

 

DP[3][3] = DP[3][2] + DP[2][3] = 4 + 6 = 10

 

위 경우를 반복하여 DP를 구성한 뒤 DP[N][K]을 결과로 출력합니다.

 

문제에 해결알고리즘은

1. 입력값을 받아서 규칙을 적용해서 DP[][]를 구성합니다.

2. DP[N][K]을 1,000,000,000나눈 나머지를 출력합니다.

 

※DP[0][1~K]의 모든 값은 1로써 초기화해주었습니다.

DP[0][1~K]가 1인 이유는 0을 몇 번을 사용하든 경우의 수가 1번이기 때문입니다.

 

DP[0][1] = {0}

 

DP[0][2] = {0 + 0}

 

DP[0][3] = {0 + 0 + 0}

 

...

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 통해 N과 K를 띄어쓰기 기준 분리하였습니다.
• DP[0][1~K]의 값을 1로 초기화해주는 init 함수를 만들었습니다.
• 규칙을 적용하여 DP를 구성하는 cal함수를 만들었습니다.
• BufferedWriter에 DP[N][K]값을 1,000,000,000나눈 나머지 값을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• cal은 반복문을 통해 위에 설명한 규칙을 적용시켜주었습니다.
• init는 DP[0][1~K]의 값을 1로 초기화해주었습니다.

 

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[][] DP;	//메모이제이션 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //------입력값 저장 및 배열 초기화---------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	int N =Integer.parseInt(st.nextToken());
    	int K =Integer.parseInt(st.nextToken());
    	DP = new int[N+1][K+1];
    	init(K);		//DP배열 초기화 함수 실행
    	cal(N, K);		//DP구성하는 함수 실행
    	bw.write(DP[N][K] + "\n");		//DP[N][K] BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //규칙 적용하여 DP구성하는 함수
    static void cal(int n, int k) {
    	for(int i=1;i<=n;i++) {
    		for(int j=1;j<=k;j++) {
            		//결과를 1,000,000,000나눈 나머지를 출력하기 때문에 나머지를 구한다.
    			DP[i][j] = (DP[i][j-1] + DP[i-1][j]) % 1000000000;
    		}
    	}
    	return;
    }
    //DP[0][1~K] = 1로 초기화하는 함수
    static void init(int k) {
    	for(int i = 1;i<=k;i++)
    		DP[0][i] = 1;
    	return;
    }
}