BOJ_1010 : 다리 놓기

👉 문제링크

1010번: 다리 놓기

---

---

🔸 문제 분석 🔸

• N개의 서쪽 지점에서 M개의 오른쪽 지점으로 다리를 연결 하는 경우의 수를 구한다.
  • 다리는 서로 겹칠 수 없다.
  • 한 지점은 하나의 다리만 놓일 수 있다.
• 조합으로 접근할 수 있다.
  • N <= M 에서 다리를 가장 많이 놓으려면 N개를 놓아야 한다.
  • M개에서 N개를 선택해야하며 중복되지 않아야 한다. (mCn)
  • 조합은 순서를 고려하지 않으므로 다리가 겹치면 안된다는 조건은 상관없어진다.
  • 조합의 성질을 이용해 메모이제이션으로 동적계획법을 사용할 수 있다.
    • n C 0 = n C n = 1 
    • n+1 C r+1 = n C r + n C r+1 이므로,
      n C r = n-1 C r-1 + n-1 C r 이 가능하다.

🔸 코드 🔸

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

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

        int[][] dp = new int[30][30];
        for (int i = 0; i < 30; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0 || i==j) dp[j][i] = 1;
                else {
                    dp[j][i] = dp[j-1][i-1] + dp[j][i-1];
                }
            }
        }

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());
            System.out.println(dp[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())]);
        }
    }
}

🔸 코드 해석 🔸

• 위 조합의 성질 공식을 바텀 업 방식으로 구현하면 dp배열을 채워가는 방식으로 답을 구할 수 있다.

---

🔸 end 🔸

• 조합을 재귀로 접근하면 그렇게 어렵지 않지만, 메모이제이션을 위해 dp배열을 바텀 업 방식으로 채우는 방법은 조합 공식을 알 필요가 있어서 포스팅을 참고했다. (참고 포스팅)