[Algorithm] 다리놓기

이번 문제는 다리를 짓는 경우의 수에 대한 문제다. 물론 다리가 겹치지 않게 지어야

한다는 조건이있다. 이번 문제는 쉽게 해결 할 수 있었다.

먼저 [N][M]을 행렬로 갖는 이차배열을 생성 한다음 N일때 M 포인트로 연결 할 수 있는

경우의 수를 계산하였다.

와 같은 점화식을 생성하여 해결하였다.

Source:
import java.io.*;
import java.util.*;
public class a_1010 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int N,M;
long [][]C;
StringTokenizer st;
for(int i=0;i<T;i++){
long res=0;
st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
C = new long[N][M];
for(int j=0;j<M-N+1;j++) C[0][j]=1;

for(int k=1;k<N;k++){
for(int t=k;t<M-N+k+1;t++){
for(int u=0;u<t;u++){
C[k][t]+=C[k-1][u];
}
}
}
for(int k=0;k<M;k++) res+=C[N-1][k];
System.out.println(res);
}

}

}