[BOJ1010] 다리 놓기

문제 유형: 조합론, 다이나믹 프로그래밍

문제 링크

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

풀이

0. 문제 해석

강의 서쪽과 동쪽에 각각 N개, M개의 사이트가 존재한다. 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하는데, 이때 다리끼리는 서로 겹쳐질 수 없다는 조건이 있다. N개의 다리를 놓는 총 경우의 수를 구하는 문제이다.

1. 접근 방법

다리가 서로 겹쳐지지 않으려면, 서쪽의 사이트들을 순서대로 1부터 N이라 하고, 동쪽의 사이트들을 순서대로 1부터 M이라고 가정해보자. 만약 서쪽의 i번째 사이트가 동쪽의 j번째 사이트와 연결된다면, 서쪽의 i+1번째 사이트는 필연적으로 동쪽의 j보다 큰 번호의 사이트와 연결되어야 한다.

이 규칙은 결국, 동쪽의 M개 사이트 중에서 N개를 선택하기만 하면, 다리를 연결하는 방법은 오직 한 가지로 결정된다는 것을 의미한다. 예를 들어, 동쪽에서 1, 3, 4번 사이트를 선택했다면, 서쪽의 1번은 동쪽의 1번, 서쪽의 2번은 동쪽의 3번, 서쪽의 3번은 동쪽의 4번과 연결되는 단 한 가지 경우만 존재하게 된다.

따라서 이 문제는 동쪽 사이트 M개 중 N개를 순서 없이 선택하는 조합(Combination) 문제, 즉 mCn을 계산하는 문제로 귀결된다.

2. 아이디어

조합 nCr을 계산하는 방법에는 여러 가지가 있지만, N과 M의 범위가 최대 30으로 크지 않으므로, 동적 계획법(Dynamic Programming)을 사용하여 조합 테이블을 만들 수 있다.

조합의 중요한 성질인 파스칼의 삼각형(Pascal's Identity)을 활용한다.

nCr = n-1Cr-1 + n-1Cr

이 점화식을 사용하여 dp[i][j]를 iCj의 값으로 정의하고, dp 테이블을 채워나가는 방식으로 문제를 해결한다. dp[m][n]이 최종적인 정답이 된다.

3. 동작 방식

dp 배열을 int[M+1][N+1] 크기로 선언하여 mCn 값을 저장할 공간을 마련한다. 이후 점화식을 적용하기 위한 초기값을 설정한다.

• dp[i][1] = i : i개 중 1개를 뽑는 경우의 수는 i이다 (iC1 = i).
• dp[i][i] = 1 : i개 중 i개를 모두 뽑는 경우의 수는 1이다 (iCi = 1).

이중 반복문을 사용하여 파스칼의 점화식 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]을 적용하여 dp 테이블을 채운다. 바깥쪽 루프는 i가 3부터 M까지, 안쪽 루프는 j가 2부터 N까지 순회하며, 이전에 계산된 값을 바탕으로 현재의 조합 값을 계산한다.

모든 계산이 끝난 후, dp[M][N]에 저장된 값이 문제의 정답이므로 이를 출력한다. 소스코드에는 M == N일 때 1, N == 1일 때 M을 출력하는 분기 처리가 있는데, 이는 DP 테이블을 모두 채우기 전에 더 빠르게 답을 찾을 수 있는 특정 경우를 처리하는 부분이다.

4. 코드

package BOJ1010;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[][] dp;
    static int N, M;

    //mCn = m-1Cn + m-1Cn-1
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            dp = new int[M + 1][N + 1];// nCr을 구하는 조합
            if (M == N) {
                System.out.println(1);
                continue;
            }
            if (N == 1) {
                System.out.println(M);
                continue;
            }
            dp[0][0] = 0;
            dp[2][1] = 2;
            for (int i = 1; i <= M; i++) {
                dp[i][1] = i;
                if (i <= N) {
                    dp[i][i] = 1;
                }
            }
            for (int i = 3; i <= M; i++) {
                for (int j = 2; j <= N; j++) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }
            System.out.println(dp[M][N]);

        }
    }

}