[BOJ_1010] 다리놓기

설명

---

한방에 통과 할 수 있었는데 처음에 언어 선택을 잘 못 했다가 컴파일 에러를 출력해버린 문제입니다.

 

정리하고 문제 분석을 해보면 N 노드에서 M 노드까지 연결을 할 수 있는 경우에 수를 출력하면 되는 문제인데요. 이는, N <= M 조건이므로 M에서 N개를 선택한다고 보아야겠습니다. 조합(해당 문제는 순서를 고려 하지 않기 때문에 사용합니다.)의 경우를 생각해보면 mCn을 구현 할 것  같습니다.

 

하지만, 이는 시간 초과를 야기하고 이를 방지하기 위해서는 조합의 유명한 공식인 nCr = n-1Cr-1 + n-1Cr 을 사용합니다.

 

이를 동적 계획법에 따라서 만들게 되면 dp[i][j] = 1 , dp[i][0] = 1 M 이 i이고 N이 j이라고 생각합시다. 그렇게 보면 i개 중에 i개 뽑는 경우는 1개 이고 i개 중에 0개 뽑는 경우도 1개 입니다. 무조건 

 

그래서 해당 식으로 dp[i][j] = dp[i - 1][j] + dp[i-1][j-1] 이라는 점화식을 만들어서 조합의 경우의 수를 메모리제이션으로 구합니다.

코드

---

import java.util.Scanner;

public class BOJ_1010 {
    static long[][] dp = new long[31][31];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        for (int i = 0; i < 31; i++) {
            dp[i][i] = dp[i][0] = 1;
            for (int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }

        for (int i = 0; i < T; i++) {
            int N = scanner.nextInt();
            int M = scanner.nextInt();
            System.out.println(dp[M][N]);
        }
    }
}

 

1010번: 다리 놓기