Q1010. 다리놓기

조합으로 풀수있지만, DP공부중이기 때문에, DP로 풀었습니다.

하나하나 작성하며 규칙을 찾았습니다.

규칙은 다음고 같습니다.

F(n, m) = F(n, m-1) + F(n-1, n-1)

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q1010 { static int[][] array; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int testCase = Integer.valueOf(st.nextToken()); for (int t = 1; t <= testCase; t++) { st = new StringTokenizer(br.readLine()); int leftNum = Integer.valueOf(st.nextToken()); int rightNum = Integer.valueOf(st.nextToken()); array = new int[rightNum+1][rightNum+1]; for (int i = 1; i <= rightNum; i++) { for (int j = 1; j <= rightNum; j++) { if (i == 1) { array[i][j] = j; } else { array[i][j] = array[i][j-1] + array[i-1][j-1]; } } } System.out.println(array[leftNum][rightNum]); } } }