[백준] 1010번: 다리 놓기 (Java)

1. 문제설명

도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강의 흐르고 있다. 다리를 짓기로 하고, 짓기에 적합한 곳(사이트)이 서쪽에 N개, 동쪽에는 M개가 있다.(N≤M) 한 사이트에는 최대 한 개의 다리만 연결될 수 있고, 다리를 최대한 많이 짓기 위해 서쪽의 사이트 개수만큼(N개) 다리를 지으려고 한다.

다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 문제이다.

• 시간 제한: 0.5초
• 메모리 제한: 128MB

 

2. 접근 방식

• 조합의 개념을 사용한다.
  • $_nC_r$ : 서로 다른 n개의 원소에서 r(단, $0< r ≤ n$)개를 중복없이, 순서를 고려하지 않고 선택하는 것
  • $_nC_r = {_{n-1}C_{r-1}} + {_{n- 1}C_{r}}$
• int dp[][] 배열을 사용하여 조합의 값을 저장한다.
• DP의 Top-Down 방식을 사용한다.
  • ${_{n-1}C_{r-1}}$과 ${_{n- 1}C_{r}}$을 재귀 호출을 통해 $_nC_r$의 값을 저장한다.
  • n이 r과 같거나, r이 1이면, 해당 배열에 1을 저장하고 반환한다.
  • 마지막으로 $_nC_r$의 값을 반환한다.

 

3. 최종 코드

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

public class Main {
    static int n, m;
    static int[][] dp; // 조합의 값을 저장할 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while(t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            dp = new int[m+1][m+1]; // dp 배열 초기화

            // m개 중에서 n개를 선택하는 조합의 경우의 수를 구함
            System.out.println(combination(m, n));
        }
    }
    
    static int combination(int n, int r) {
        // 이미 계산을 한 경우, 그 값을 반환
        if(dp[n][r] > 0) return dp[n][r];
        // nCn 또는 nC1이면 값은 1로 반환
        if(n==r || r==0) return dp[n][r] = 1;

        // 재귀 호출을 통해 점화식을 만족하는 조합의 값을 계산
        dp[n][r] = combination(n-1, r-1) + combination(n-1, r);
        return dp[n][r]; // nCr 값을 반환
    }
}

 

4. 느낀점 or 기억할정보

문제를 보고 조합 개념을 사용하면 된다는 것은 바로 파악했지만, 점화식은 찾아보게 되었다.