[DP] 백준 - 합분해

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

2225번: 합분해

 

-문제해설

손으로 직접 다 써봤더니 점화식을 세울 수 있는 규칙을 찾을 수 있었다. 화질이 구려도 알아볼 수는 있으니 ㅎㅎ

맨 위 사진에서보면 일단 n이 1일 때 k이 증가함에 따라 나올 수 있는 개수도 1씩 증가한다.

그리고 k가 1일 때는 무조건 1이다.

나머지의 경우는 만약 ( 4, 3 )을 구한다고하면 ( 4, 2 ) + ( 3, 3 )을 더하면 나오는 것을 알 수 있다.

 

이를 코드화하면 아래와 같다.

 

 

 

-자바

package dp;

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

public class BJ2225 {

	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() );
		
		long[][] dp = new long[n+1][k+1];
		for( int i=1; i<=n; i++ ) {
			for( int j=1; j<=k; j++ ) {
				if( i==1 ) {
					dp[i][j] = j;
					continue;
				}
				if( j==1 ) dp[i][j] = 1;
				else dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1_000_000_000;
			}
		}
		System.out.println( dp[n][k] % 1_000_000_000 );
	}
}

 

-파이썬

import sys
l = sys.stdin.readline
n, k = map(int, l().split())
dp = [ [0]*(k+1) for _ in range( n+1 ) ]

for i in range( 1, n+1 ):
    for j in range( 1, k+1 ):
        if i==1: dp[i][j] = j; continue
        if j==1: dp[i][j] = 1
        else: dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000000
print( dp[n][k] % 1000000000 )