📝문제 설명

 

 


📢입출력 예시

 


✏️문제 풀이

1. 다리는 1:1 매칭으로만 연결 가능하다.

2. 크로스로 다리가 겹치면 안된다.

 

N <= M 에서 최대한 많은 다리를 놓기 위해서는 N개의 다리가 필요하다.

M개에서 다리를 놓을 포인트를 정해야 하고 즉, M개 중 N개를 선택해야 한다. 이는 조합 공식으로 mCn을 사용하면 된다.

 

예를 들어 (1,2,3,4)에서 (2,1,4)를 뽑았다 가정하면 이는 (1,2,4)나 (4,2,1) 처럼 순서가 다르게 뽑혀도 조합은 뽑는 순서를 고려하지 않기에 이 모두 1개의 경우로 본다.

 

위 그림처럼 왼쪽은 불가능하고 왼쪽은 가능하다.

 

왼쪽에서는 (2,1,4)가 오른쪽에서는 (1,2,4)가 뽑혔지만 조합의 경우는 이 둘 다 하나의 경우로 본다.

결국 조합 공식을 사용하면 서로 다른 다리가 겹치는 경우는 제외될 수밖에 없다.

 

공식으로 확인하자면

 

  • r! * (n-r)!은 중복을 제거하는 역할을 한다.

 

우리는 메모제이션을 활용하기 때문에 위 공식보다는 아래 공식을 사용할 것이다.

아래 공식은 조합론을 풀려면 무조건 알아야 하는 공식이므로 다들 외우도록 하자

 

 

package Baekjoon.DP;

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

public class Baek1010 {

    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;

        int testCase = Integer.parseInt(bufferedReader.readLine());

        for(int i=0; i<testCase; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            int r = Integer.parseInt(stringTokenizer.nextToken()); //서쪽
            int n = Integer.parseInt(stringTokenizer.nextToken()); //동쪽

            dp = new int[n+1][r+1];

            // nCr을 구하는 문제
            System.out.println(Combination(n, r));
        }
    }

    private static int Combination(int n, int r){

        if(n == r || r == 0){
            return 1;
        }

        if(dp[n][r] != 0){
            return dp[n][r];
        }

        // 점화식: mCn = [(n-1)C(r-1)] + [(n-1)C(r)]
        dp[n][r] = Combination(n-1,r-1) + Combination(n-1, r);
        return dp[n][r];
    }

}

💡새로 알게된 점

확률과 통계 공부를 다시 해보자!!


 

'📖Algorithm > DP' 카테고리의 다른 글

자바 [Programmers] 2단계 - 멀리 뛰기  (0) 2024.12.06
자바 [Algorithm] DP - 백준 11058 크리보드  (0) 2024.05.22