[JAVA] 백준 1010 조합+DP

 

 

 

 

1010번: 다리 놓기

문제

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

풀이

강 서쪽 사이트와 동쪽 사이트의 연결할 수 있는 경우의 수를 구하는 문제이다.

여기서 강 서쪽의 사이트가 항상 동쪽의 사이트보다 작거나 같기 때문에 동쪽 사이트 수 Combination 서쪽 사이트 수를 풀어내면 된다.

나는 여기서 조합의 점화식을 이용해서 경우의 수를 모두 구한후 계산하였다.

📌 모든 경우의 수 구하기

        int[][] A = new int[31][31];

        for(int i=0; i<A.length; i++){
            A[i][i] = 1;
            A[i][0] = 1;
            A[i][1] = i;
        }

        for(int i=1; i<A.length; i++){
            for(int j = 1; j<A.length; j++){
                A[i][j] = A[i-1][j-1] + A[i-1][j];
            }
        }

여기서 사이트의 개수는 30보다 작거나 같기 때문에 31 Combination 31까지 계산했다.

📌 출력

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for(int i=0; i<T; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(A[b][a]).append("\n");
        }
        System.out.println(sb);

서쪽 사이트 a와 동쪽 사이트 b가 주어졌을 때 b에서 a개를 선택하는 경우의 수를 출력하였다.

📌 전체 코드

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

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

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

        int[][] A = new int[31][31];

        for(int i=0; i<A.length; i++){
            A[i][i] = 1;
            A[i][0] = 1;
            A[i][1] = i;
        }

        for(int i=1; i<A.length; i++){
            for(int j = 1; j<A.length; j++){
                A[i][j] = A[i-1][j-1] + A[i-1][j];
            }
        }

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for(int i=0; i<T; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(A[b][a]).append("\n");
        }
        System.out.println(sb);

    }
}

결과