[BOJ] 1010번 다리놓기 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static final int MAX = 30;
	static int T, N, M;
	static int[][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			input(br);
			process();
			print();
		}
	}

	private static void input(BufferedReader br) throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		dp = new int[MAX][MAX];
	}

	private static void process() {
		// dp 테이블 초기화
		for (int i = 0; i < MAX; i++) {
			dp[i][i] = 1;
			dp[i][0] = 1;
		}
		// 연산 수행(이항 계수 구하기)
		for (int i = 2; i < MAX; i++) {
			for (int j = 1; j < MAX; j++) {
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
			}
		}
	}

	private static void print() {
		System.out.println(dp[M][N]);
	}
}

📄 해설

• M 개 중 N 개를 뽑아야하는 경우이며, 각각의 값이 다음 값을 구할 때 중복적으로 적용이 되는 이항계수 구하기 알고리즘을 활용하여 푸는 문제

• 이항계수를 구하는 공식은 아래와 같음
  

• 이항계수 구하기 알고리즘은 아래와 같음

  int[][] dp = new int[N + 1][K + 1];
  
  			// 2번 성질 (n == k)
  			for (int i = 0; i <= K; i++) {
  				dp[i][i] = 1;
  			}
  		
  			// 2번 성질 (k == 0)
  			for(int i = 0; i <= N; i++) {
  				dp[i][0] = 1;
  			}
  			// N개에서 K개를 고름
  			for (int i = 2; i <= N; i++) {
  				for (int j = 1; j <= K; j++) {
  					// 1번 성질 
  					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
  				}
  			}