[P&B] #110 BAEKJOON 1010

백준 1010번 다리 놓기 JAVA

문제 설명

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

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

 

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

 

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

 

나의 문제 풀이 코드

 

문제 풀이 코멘트

주어진 문제는 조합론(Combination)을 사용하여 푸는 것입니다. 주어진 도시의 서쪽과 동쪽 사이트 개수(N과 M)를 이용하여 다리를 지을 수 있는 경우의 수를 구하는 문제입니다.

이 문제가 왜 조합으로 푸는 문제인 것인지 이해가 잘 안되었습니다.

 

문제를 조합으로 푸는 이유:

문제에서 주어진 조건은 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려는데, 한 사이트에는 최대 한 개의 다리만 연결될 수 있다는 것입니다. 이러한 조건에서 서쪽 사이트 중에서 N개를 선택하여 동쪽 사이트와 연결하는 경우의 수를 구해야 합니다.

이때, 조합은 서쪽에서 N개의 사이트를 선택하는 경우의 수를 나타냅니다. 서쪽 사이트 중에서 N개를 선택하는 방법의 수는 동쪽 사이트와의 다리를 어떻게 연결할지에 대한 문제와 관련이 있습니다. 따라서 이 문제를 조합을 사용하여 푸는 것은 서쪽 사이트를 선택하는 방법의 수를 계산하는 데 도움이 됩니다.

다리끼리 겹치지 않도록 하는 방법:

다리끼리 겹치지 않도록 하는 조건은 문제에서 주어진 것처럼 서쪽 사이트 중에서 N개를 선택하고, 이 선택한 N개의 사이트에 동쪽 사이트를 연결하는 방법을 고려하면 됩니다. 다리가 겹치지 않으려면 서쪽 사이트 중에서 선택한 사이트 간에 다리가 겹치지 않도록 배치해야 합니다.

이것은 서쪽 사이트를 순서대로 나열하는 것과 관련이 있습니다. 예를 들어, 서쪽 사이트를 1부터 N까지 순서대로 나열했다고 가정하면, 동쪽 사이트를 연결하는 방법은 서쪽 사이트를 순서대로 선택하는 것과 동일합니다. 따라서 조합을 사용하여 서쪽 사이트 중에서 N개를 선택하는 경우의 수를 구하면, 다리끼리 겹치지 않도록 서쪽 사이트를 선택하는 방법의 수를 구할 수 있습니다.

즉, 조합을 사용하여 서쪽 사이트 중에서 N개를 선택하고, 이 선택한 N개의 사이트를 순서대로 나열하는 방법의 수를 계산하면, 다리끼리 겹치지 않는 경우의 수를 구할 수 있게 됩니다. 이러한 방식으로 문제를 푸는 것이 조합을 사용하는 이유이며, 이를 통해 주어진 조건을 만족시킬 수 있습니다.

 

코드

코드에서 가장 중요한 부분은 조합을 계산하는 부분입니다. 일반적으로 조합을 계산할 땐 아래와 같은 코드를 주로 사용합니다.

static long combination(int n, int k) {
        if (k == 0 || n == k) {
            return 1;
        }
        return combination(n - 1, k - 1) + combination(n - 1, k);
}

이렇게 풀어도 조합은 구해지지만 시간복잡도가  O(T * 2^n)로 매우 높아 시간초과가 발생합니다.

정답 코드를 보면 조합을 계산하기 위한 동적 프로그래밍(Dynamic Programming)을 사용하여 조합(Combination) 값을 계산하는 함수입니다. 여기에서 조합은 "n개 중에서 k개를 선택하는 경우의 수"를 의미합니다.

 먼저 long[][] dp = new long[n + 1][k + 1]로 이차원 배열 dp를 선언합니다. dp[i][j]는 i개 중에서 j개를 선택하는 경우의 수를 저장하는 배열입니다. 여기서 n은 서쪽 사이트의 개수, k는 동쪽 사이트의 개수를 나타냅니다.
 for (int i = 0; i <= n; i++) 반복문은 현재 선택할 수 있는 사이트의 개수를 나타냅니다. 예를 들어, i가 3이라면, 3개 중에서 사이트를 선택하려는 경우를 고려하고 있습니다.
 for (int j = 0; j <= Math.min(i, k); j++) 반복문에서는 j를 0부터 i와 k 중 작은 값까지 반복합니다. 즉, 현재까지 선택한 사이트의 개수를 나타냅니다. 예를 들어, i가 3이고 k가 2라면, 현재까지 2개의 사이트를 선택한 경우를 고려하고 있습니다.
 j == 0 || j == i 라는 조건은 현재 선택한 사이트의 개수가 0 또는 i(현재 선택할 수 있는 사이트의 최대 개수)인 경우를 처리합니다. 이 경우, 다리를 건설하는 방법은 하나뿐이므로 dp[i][j]를 1로 초기화합니다. 예를 들어, 3개 중에서 0개를 선택하거나 3개 중에서 3개를 선택하는 경우는 모두 1가지 방법밖에 없습니다.
 그 외의 경우, 현재 선택한 사이트의 개수가 0이나 i가 아닌 경우를 처리합니다. 이 경우, 이전 단계의 조합 결과를 이용하여 현재 조합 값을 계산합니다. 이것은 파스칼의 삼각형을 사용한 조합 계산입니다. dp[i-1][j-1]은 j개를 선택하는 조합에 i번째 사이트를 추가한 경우를 나타냅니다. dp[i-1][j]은 j개를 선택하는 조합에 i번째 사이트를 추가하지 않은 경우를 나타냅니다. 이 두 값을 더하면 dp[i][j]를 구할 수 있습니다.
 이렇게 계산된 dp[n][k] 값은 "n개 중에서 k개를 선택하는 경우의 수"를 나타냅니다. 이러한 방식으로 문제를 풀면 시간 복잡도가 O(T * M * N)이 됩니다. 따라서 주어진 문제에서는 "서쪽 사이트 중에서 N개를 선택하고, 동쪽 사이트 중에서 M개를 선택하는 경우의 수"를 빠르게 구하기 위해 calculateCombination(M, N) 함수를 호출합니다.