[백준-1010] 다리 놓기 - Java

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

1010번: 다리 놓기

조합을 사용하면 해결된다.

aCb = a-1Cb-1+a-1+Cb

 

코드

import java.util.*;

public class back1010 {

    static int [][]arr=new int[30][30];

    public static void main(String args[]){

        Scanner scanner=new Scanner(System.in);

        int num=scanner.nextInt();

        for(int i=0;i<num;i++){

            int b=scanner.nextInt();

            int a=scanner.nextInt();

            System.out.println(combi(a,b));

        }

    }

    static int combi(int a, int b){

        if(arr[a][b]>0){

            return arr[a][b];

        }

        if(a==b||b==0){

            return arr[a][b]=1;

        }

        return arr[a][b]=combi(a-1,b-1)+combi(a-1,b);

    }

}