[백준 1010] 다리 놓기

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

1010번: 다리 놓기

 

백준 1010번 문제 다리 놓기 입니다.

 

dp(dynamic programming)를 공부하면서 풀어 본 문제입니다.

 

---

문제를 간단하게 요약하면 강을 기준으로 서쪽과 동쪽이 있고 다리를 건설할 수 있는 위치 사이트가 있습니다.

서쪽 사이트 N개, 동쪽 사이트 M개입니다. (N<=M)

이때 다리는 서로 교차되어서는 안됩니다.

 

이 문제는 조합 문제로 푸는 방법만 안다면 수월하게 풀 수 있는 문제입니다.

 

우선, 조합 문제인 이유부터 알아 보겠습니다.

 

• 동쪽 사이트 M개 중에서 서쪽 사이트 N개를 고르는 경우에 수를 구하는 것입니다.
• 동쪽 사이트(1,2,3)이 있고 서쪽 사이트(1,2) 가 있을 경우 3개중에 2개를 고르는데 (1,2)를 고르는 것과 (2,1)를 고르는 것은 하나를 고르는 것으로 보면 됩니다.
• 따라서, mCn의 개수를 구하면 이 문제의 답을 알 수 있습니다.

하지만 여기에는 함정이 있죠!

그림을 보면서 확인해보겠습니다.

 

위의 사진은 제가 그린.. 조합을 구하는 그림입니다. (파스칼 삼각형이에요~)

사진에 살짝 빠진 부분이 있는데

4c2를 구하기 위해서 사실.. 3c1과 3c2를 더하면 됩니다.

점화식은 mCn = m-1Cn-1 + m-1Cn이 되겠군요.

 

이제 함정을 아시겠나요?

4c2를 구하는 과정을 한번 알아보시죠!

• 4c2 = 3c1 + 3c2
• 3c1 = 2c0 + 2c1
• 3c2 = 2c1 + 2c2
• 2c1 = 1c0 + 1c1

이렇게 되는데.. 2c1은 두곳에서 사용이 되는군요 지금은 4c2를 구하는데 10c3을 구한다면 2c1은 정말 많이 사용될거 같네요..

여기서 바로 dp 문제 접근 방법으로 해결할 필요가 있습니다.

바로 Memorization(메모리제이션) 입니다!

 

미리 2c1을 한번만 구하고 필요로 하는 다른곳에서 꺼내가는 겁니다.

 

마지막 최종 풀이

• m과 n이 많아야 30이기 때문에 int[][] dp = new int[31][31]을 만듭니다.
• 만약dp[m][n]의 값이 존재한다면 그 값을 return하면 됩니다. (이미 계산한 값이 저장되어 있는 것이기 때문!)
• 만약 m=n이거나 n이 0이면 1을 return 합니다.
• 그리고 위의 조건들이 아니라면 mCn = m-1Cn-1 + m-1Cn 이 점화식에 맞춰서 다시 함수를 호출하면 됩니다.

---

코드

package codingtest.building_bridge;

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

public class Main {

    static int[][] dp = new int[31][31];

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

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

        for(int i = 0; i<c;i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            System.out.println(com(m,n));

        }
    }

    private static int com(int m, int n) {

        // 이미 계산된 경우
        if(dp[m][n] > 0) {
            return dp[m][n];
        }

        // 원소의 개수가 조합의 개수와 동일하거나 0인 경우
        if (n == m || n==0) {
            return 1;
        }

        return dp[m][n] = com(m-1, n-1) + com(m-1, n);
    }

}