[Java] 백준 1010번 다리 놓기

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

1010번: 다리 놓기

문제 설명

• 서쪽의 N개의 사이트와 동쪽의 M개의 사이트를 다리로 연결할 수 있는 경우의 수 구하기 (N ≤ M)
• 한 사이트에는 최대 한 개의 다리만 연결될 수 있다
• 다리끼리는 서로 겹쳐질 수 없다

배열 dp[N][M]은 서쪽의 N개의 사이트와 동쪽의 M개의 사이트를 다리로 연결하는 경우의 수를 의미한다.

다리는 서로 겹쳐질 수 없다는 조건이 있으므로 하나의 다리를 고정해놓고 생각해보았다.

 

N=2인 경우를 생각해보자.

dp[2][1] = 0이다. -> N개의 사이트는 모두 연결되어야 하는데 N이 M보다 작기때문이다.

dp[2][2] = 1이다. -> 겹치지 않고 다리를 연결할 수 있는 경우의 수는 하나밖에 존재하지 않는다.

dp[2][3] = dp[2][2]의 경우의 수 + dp[1][2]의 경우의 수 = 3이다. -> 이전의 구했던 경우의 수 중 하나의 다리를 고정시켜 놓고 나머지 N개의 다리와 M개의 다리를 연결할 수 있는 경우의 수를 더해주는 것이다.

dp[2][4] = dp[2][3]의 경우의 수 + dp[1][3]의 경우의 수 = 10

 

dp[2][4] 경우의 수 구하기

즉, dp[N][M] = dp[N][M-1] + dp[N-1][M-1]

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
		
		Scanner s= new Scanner(System.in);
	
		int T =s.nextInt(); //테스트 케이스 개수
		
		for(int i=0;i<T;i++) {
			int N= s.nextInt();
			int M = s.nextInt();
			
			int dp[][] = new int[N+1][M+1];
			
			for(int n=2;n<=N;n++)
				dp[n][1]=0;
			
			for(int m=1;m<=M;m++)
				dp[1][m]=m;
			
			
			for(int x=2;x<=N;x++) {
				for(int y=2;y<=M;y++) {
					dp[x][y]=dp[x][y-1]+dp[x-1][y-1];
				}
			}
			
			System.out.println(dp[N][M]);
		}
		
		
	}
}