백준-2225번/합분해 (java)

 

K개의 숫자로  N을 만들어야한다.

이 문제의 핵심적으로 구현해야 하는 로직은 숫자 X가 더해진다면  K-1개의 숫자로 N-X를 만들어야 한다는 것이다.

ex)

N=2인경우(k=2)

맨 앞 수가 0이 올때 + (남은 한자리로 2를 만들어야 한다.(k=1,N=2))

맨 앞 수가 1이 올때 + (남은 한자리로 1을 만들어야 한다.(k=1,N=2))

맨 앞 수가 2가 올때 + (남은 한자리로 0을 만들어야 한다.(k=1,N=2))

 

 

이를 점화식으로 표현한 코드는 다음과 같다.

for(int i=2; i<k+1; i++) {
			for(int j=1; j<n+1; j++) {
				for(int a=0; a<=j; a++) {
					dp[i][j]=(dp[i][j]+dp[i-1][a])%1000000000;	
				}
			}
		}

 

주의 할 점.

k=1일때는 N이 뭐든지 경우의 수가 1가지만 나온다. 

N=0일때는 k가 뭐든지 경우의 수가 1가지만 나온다. 

이 점을 코드에 반영해줘야 한다.

따라서 점화식을 구현하기 전 dp배열을 초기화 해줘야한다.

 

정답 코드

import java.util.Scanner;

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

 

 

느낀점 : 이차원 배열을 이용한 다이나믹 프로그래밍 연습이 더 필요하다.