(JAVA) 백준 1010번 : 다리 놓기

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

1010번: 다리 놓기

이 문제도 전에 풀었던 이항 계수 1, nCr 을 구하는 풀이와 같다.

이번에도 동적계획법 DP 를 이용하여 풀이를 구했다.

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	static int[][] dp;
 
	public static void main(String[] args) throws IOException 
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
        
        // 0 <= N <= M <= 30
		dp = new int[30][30];
		while(T-- >0)
		{
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());

			System.out.println(BC(K, N));
		}
	}
 
	// 이항계수 nCr
	static int BC(int n, int k) 
	{
		// 이미 풀었던 sub문제일 경우 값을 재활용
		if (dp[n][k] > 0) 
		{
			return dp[n][k];
		}
 
		// 2번 성질
		if (n == k || k == 0) 
		{
			return dp[n][k] = 1;
		}
 
		// 1번 성질, 2번 성질을 만족할 때까지 줄여가는 방식
		return dp[n][k] = BC(n - 1, k - 1) + BC(n - 1, k);
	}
}