PS/BOJ2022. 4. 27. 00:25

합분해

 

DP[K][N]

초기화


DP[K][0]=1  => 0을 0으로 표현, 자리수 관계없이 -> 1가지 ex) 0,0,0 K=3,N=0
K=1 DP[1][N]=1   => ex) 5를 1자리에 표현
K=2 DP[2][N]=N+1 
=> ex) 5를 하나씩 옆자리로 옮기면서 표현

5,0
4,1
3,2
2,3
1,2
0,5

0~5까지 세는 것과 동일


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

...


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


0,1,0
0,0,1 => DP[2][1] : 0을 고정하면, K=2일때 1을 표현하는 방법
1,0,0 => DP[2][0] : 1을 고정하면, K=2일때 0을 표현하는 방법

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

2,0,0 => DP[2][0] : 2를 고정하면, K=2일때 0을 표현하는 방법
1,1,0 => DP[2][1] : 1을 고정하면, K=2일때 1을 표현하는 방법

0,1,1
0,2,0
0,0,2 => DP[2][2] : 0을 고정하면, K=2일때 2를 표현하는 방법


점화식 도출
DP[K][N] = DP[K-1][N] + DP[K-1][N-1] + DP[K-1][N-2] + …. + DP[K-1][1] + DP[K-1][0] 

 

 

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

public class Main {

	static long[][] dp;
	static long MOD = 1000000000L;

	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 = new long[205][205];

		for (int i = 0; i <= K; ++i)
			dp[i][0] = 1;
		for (int i = 0; i <= N; ++i) {
			dp[1][i] = 1;
			dp[2][i] = i + 1;
		}

		for (int i = 3; i <= K; ++i) {
			for (int j = 1; j <= N; ++j) {
				for (int k = 0; k <= j; ++k) {
					dp[i][j] += dp[i - 1][k]%MOD;
				}
			}
		}

		System.out.println(dp[K][N]%MOD);

	}

}

 



 

 

백준_2225_합분해.xlsx
0.01MB

'PS > BOJ' 카테고리의 다른 글

2011  (0) 2022.04.28
11052  (0) 2022.04.27
2133  (0) 2022.04.26
1699  (0) 2022.04.26
2579  (0) 2022.04.25
Posted by easy16