백준 1010번 - 다리 놓기

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

1010번: 다리 놓기

 

다음 문제는 확통에서 배운 nCr 을 사용하면 풀린다.

여기서 nCr = n-1Cr + n-1Cr-1 법칙을 사용하면 다음 코드로 풀린다.

 

 

여기서 nCr = n-1Cr + n-1Cr-1 법칙을 사용하면 다음 코드로 풀린다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
	static int[][] dp = new int[30][30];
	public static void main(String[] args) throws IOException {
		 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			System.out.println(func(b,a));
		}
		
	}
	static int func(int a, int b) {
		if(dp[a][b]>0)
			return dp[a][b];
		else if(a==b||b==0)
			return dp[a][b]=1;
		else
			return dp[a][b] = func(a-1,b) + func(a-1,b-1);

	}
}