[BaekJoon] 1010 다리 놓기 (Java)

🔗 문제 링크

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

📝 문제풀이 방법

문제의 조건을 읽어보면 N ≤ M이라는 규칙이 존재한다. 또한 다리를 서로 겹칠 수 없다는 조건을 통해 M개의 점에서 N개의 점을 선택하면 해당 순서는 자동으로 정해져 해당 문제는 Combination을 구하는 문제임을 알 수 있었다.

문제를 효울적으로 풀기 위해서는 DP식으로 코드를 작성하였으며 규칙은 아래의 $nCr$의 성질을 사용하여 풀었습니다.

👨🏻‍💻 작성한 코드

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for (int i=0; i<T; i++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			bw.write(combination(N, M)+"\n");
		}
		bw.flush();
		bw.close();
		br.close();

	}
	static int combination(int N, int M) {
		int[][] dp = new int[N+1][M+1];
		for(int i=2;i<=N;i++)
			dp[i][1]=0;
		
		for(int i=1;i<=M;i++)
			dp[1][i]=i;
		
		for(int i=2;i<=N;i++) {
			for(int j=2;j<=M;j++) {
				dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
			}
		}
		return dp[N][M];
	}

}