[BOJ 1010] 다리 놓기 (Java)

문제

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

풀이

서쪽의 N개의 다리가 있고 동쪽에 M개의 다리가 있다. 

다리를 겹치지 않게 배치할 수 있는 경우의 수는, 강 동쪽에서 M개의 다리 중 N개의 다리를 순서 없이 선택하는 경우의 수와 동일하다. 

 

메모제이션 기법과 조합의 성질로 해당 문제를 풀 수 있다. 

알아야 할 조합의 성질 

• nCn = 1, nC0 = 1
• nCm = n-1Cm-1 + n-1Cm

https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9

조합 - 위키백과, 우리 모두의 백과사전

 

소스코드

package math;

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

public class BOJ1010 {

    public static Integer memozation[][];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        memozation = new Integer[30][30]; // N, M 범위 1~29
        StringTokenizer st = null;
        for(int i = 0; i < T; i++){
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            // n개의 다리중 m개 선택
            bw.write(combination(n, m) + "\n");
        }
        bw.flush();
    }

    public static int combination(int n, int m){
        // nCm
        // nCm = n-1Cm-1 + n-1Cm
        if(n == m || m == 0) return 1;
        if(memozation[n][m] != null) return memozation[n][m];

        memozation[n][m] = combination(n-1, m-1) + combination(n-1, m);
        return memozation[n][m];
    }

}