[알고리즘/백준] 1010번 : 다리 놓기(Java)

문제	1010번 : 다리 놓기
문제링크	https://www.acmicpc.net/problem/1010
난이도	S5
언어	Java
분류	DP | 수학, 다이나믹 프로그래밍, 조합

 

 

📌 최종 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static int[][] dp;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		dp = new int[30][30]; // n,r의 값(nCr) 담을 배열
		
		// Test case 개수 T 입력
		int t = Integer.parseInt(br.readLine());
		
		for(int i=0; i<t; i++) {
			String[] input = br.readLine().split(" ");
			int n = Integer.parseInt(input[0]); // 서쪽 사이트 개수 N
			int m = Integer.parseInt(input[1]); // 동쪽 사이트 개수 M
			
			bw.write(fn_result(m,n) + "\n");
		}
		
		bw.flush();
		bw.close();
		
		br.close();
	}

	private static int fn_result(int n, int r) {
		// 배열 값이 0보다 크면 값이 존재하므로 계산 끝
		if(dp[n][r] > 0) { 
            return dp[n][r];
        }

		// 기본 조합: nCn 또는 nC0 = 1
        if(n == r || r == 0) {
        	// n개 중 n개를 고르는 경우, n개 중 0개를 고르는 경우 = 1가지
            return dp[n][r] = 1;
        }

        /*
         	조합의 점화식 : 어떤 요소를 선택하는 경우와 선택하지 않는 경우로 나눠서 계산하는 방식
			
			5개 중에서 3개를 고르는데, 하나의 특정 원소 X를 기준으로 나누어 생각
			X를 포함하는 경우 → 나머지 4개 중 2개를 고르면 됨 → 4C2
			X를 포함하지 않는 경우 → 나머지 4개 중 3개를 고르면 됨 → 4C3

			→ 5C3 = 4C2 + 4C3 → nCr = (n−1)C(r−1) + (n−1)Cr
         */
        return dp[n][r] = fn_result(n-1, r-1) + fn_result(n-1, r);
	}
}

📌 구해야 하는 정답

- 각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력

📌 코드 설계하기

- 한 사이트에는 한 개의 다리만 놓일 수 있음
- 서로 다른 다리가 겹치면 안 됨

 

1. Test case 개수 입력

2. 서/동쪽 사이트 개수 입력

3. 경우의 수 계산 및 출력
  - M개 중 N개를 중복 없이 선택 (N ≤ M)
  -> 조합 : 서로 다른 n개에서 r개를 뽑기. nCr