백준 [1010] 다리 놓기 (JAVA)

문제

풀이

서쪽과 동쪽 사이트를 다리로 연결하는데 한 사이트에는 최대 한 개의 다리만 연결할 수 있다.

 

다리를 최대한 많이 짓는 경우(N개)를 가정

다리끼리 서로 겹칠 수 없다.

 

N보다 M의 갯수가 더 많다고 문제 조건에 주어져 있다. N개를 모두 빠짐 없이 고르는 경우의 수들을 체크해야 한다. M개 중 N개를 택하는 경우 -> 조합을 사용한다.

조합을 사용할 경우 다리가 겹치는 문제도 해결할 수 있다. 조합은 중복을 허용하지 않기 때문이다.

이항 계수와 파스칼의 법칙을 사용하여 nCr 조합을 구현하면 된다.

 

조합 참고 사이트

https://st-lab.tistory.com/159#%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[백준] 11050번 : 이항 계수 1 - JAVA [자바]

 

2차원 dp 배열을 선언해준다. (부분 문제를 계속해서 재귀함수를 타는 것을 방지하기 위해)

 

조합 공식과 성질들을 활용하여 문제를 푼다.

 

조합 공식

 

조합 성질 1 파스칼의 법칙

간단하게 아래와 같이 표현 가능. 위 식은 파스칼의 삼각형을 생각해보면 된다.

위는 아래와 같이 표현가능

 

 

조합 성질 2

 

위 두 성질과 메모이제이션을 활용하여 구현할 수 있다.

 

정답코드

package com.baekjoon.dynamic_programming.p1010;

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

public class Main {
    static int[][] dp = new int[30][30];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            sb.append(combi(r, n) + "\n");
        }

        System.out.println(sb);
    }

    static int combi(int n, int r) {
        if (dp[n][r] > 0) {
            return dp[n][r];
        }

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

        return dp[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
    }
}