[BOJ/백준] 1010 다리 놓기 (JAVA)

링크

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

 

문제 요약

각 테스트 케이스에 대해 다리를 지을 수 있는 경우의 수 출력하기

 

강의 서쪽에는 N개, 동쪽에는 M개의 사이트가 있다.

다리끼리 서로 겹칠 수 없다.

서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다.

 

제한

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

 

풀이

보시면 시간제한이 0.5초로 매우 짧습니다. 그렇기 때문에 모든 경우를 탐색하며 문제를 풀면 안 됩니다.

 

N개의 사이트를 기준으로 다리를 짓기 때문에 N 값이 동일할 때 예제를 살펴보겠습니다.

`[N=2일 때]`

M=2: 1

M=3: 3

M=4: 6

M=5: 10

M=6: 15

…

 

답 결과가 익숙하지 않으신가요?

바로 M개중 N개를 고르는 조합 문제입니다.

 

`M=3`, `N=2`라고 합시다.

서쪽 1, 2번을 동쪽 1, 2번과 연결하는 경우는 하나입니다. 바로 1-1, 2-2로 연결되는 경우입니다.

결국, 동쪽에서 N개를 선택했을 때 서쪽 N개의 사이트와 연결할 수 있는 경우는 “하나”입니다.

따라서 동쪽 M개 중 N개를 고르는 경우의 수가 다리를 지을 수 있는 경우의 수가 되어버립니다.

 

이는 다리가 겹치지 않아야 한다는 조건 때문입니다.

만약 이 조건이 없다면 1-1,2-2 / 1-2, 2-1 순열 문제가 되어버립니다.

 

조합 문제를 보면 처음 떠올릴 수 있는 것이 factorial 함수를 재귀적으로 호출해 조합 계산하는 방식입니다.

하지만 M 값이 최대 29이고, 29 팩토리얼은 long의 범위를 넘어가기 때문에 오버플로우가 발생합니다!

 

따라서 아래 조합 성질을 이용해 dp로 문제를 풀어야 합니다.

 

코드

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

public class Main {

    static int T, N, M;
    static int[][] dp;

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

        T = Integer.parseInt(br.readLine());
        dp = new int[30][30];

        for(int i=0; i<T; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            sb.append(sol(M,N)).append("\\n"); // M개중 N개의 조합을 고르는 경우의 수
        }
        System.out.print(sb);
    }

    static int sol(int n, int r){
        if(dp[n][r] > 0) // 이미 계산한 경우
            return dp[n][r]; 
        if(n == r || r < 1){ // N개 중 N개를 고르는 경우의 수는 1 + 0개를 고르는 경우의 수는 항상 1
            return dp[n][r] = 1;
        }

        return dp[n][r] = sol(n-1, r-1) + sol(n-1, r);
    }
}

🏷 시간 복잡도

• 각 (n, r) 조합을 한 번씩만 계산하고, 가능한 (n, r) 조합은 최대 N*M개다.
• 최종 시간 복잡도: O(N*M)

🏷 실행 속도

Time: 104 ms, Memory: 14348 KB