📝문제 설명
📢입출력 예시
✏️문제 풀이
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 |