알고리즘
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--;
}
}
}
}
}