알고리즘

1010번 다리 놓기

살구르 2017. 2. 15. 15:42

// d[i][j] 는 서쪽에 있는 돌의 갯수가 i개이고, 동쪽에 있는 돌의 갯수가 j개 일 때의 경우의 수

import java.io.*;

import java.util.*;


class Main{

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

public static void main(String[] args) throws IOException{

Scanner sc = new Scanner(System.in);

int T = sc.nextInt();

solve();

for(int i=0;i<T;i++)

System.out.println(d[sc.nextInt()][sc.nextInt()]);

}

    

public static void solve(){

//d[i][j] = d[i-1][j-1]+d[i-1][j-2]+...d[i-1][i-1]

for(int i=1;i<30;i++){

d[1][i]=i;

}

for(int i=2;i<30;i++){

for(int j=i;j<30;j++){

int temp=j-1;

while(temp!=i-2){

d[i][j]+=d[i-1][temp];

temp--;

}

}

}

}

}