[Java] 백준(실버-5) 1010번 - 다리놓기

문제 분석

---

작성코드

---

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

class Main {
    static int[][] D = new int[30][30];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // N개만큼의 다리를 만들어야 하기 때문에
        // M개의 다리중에서 N개를 골라야 한다. 이를 통해, MCN이라는 조합론을 이용할 수 있다. 

        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int cnt = comb(M, N);
            bw.write(cnt+"\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static int comb(int n, int r) {    
        // DP의 메모이제이션을 활용, 이미 계산한 값이라면 바로 반환한다.
        if(D[n][r] > 0) {
            return D[n][r];
        }
        // 조합의 성질을 통해 n==r이거나 r==0이면 1을 저장한다.
        if(n == r || r == 0) {
            return D[n][r] = 1;
        }
        return D[n][r] = comb(n-1, r-1) + comb(n-1, r);
    }
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.