BOJ#1010 다리 놓기

BOJ#1010 다리 놓기

* 문제

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

* 풀이

풀이 #1. 조합

이 문제는 단순히 M개의 사이트 중에서 N개를 고르는 경우의 수를 구하는 문제입니다. 조합 : mCn

mCn = m! / {(m-n)! * n!}

풀이 #2. 동적계획법

dp[N][M] : 사이트가 각각 N개, M개일 때, 주어진 조건에 맞게 다리를 건설할 수 있는 경우의 수

dp[N][M] = dp[N-1][M-1] + dp[N-1][M-2] + ... +  dp[N-1][N-1]

---

* 나의 코드

<조합>

https://github.com/stack07142/BOJ/blob/d8bb015604a276ecd8643e16c9ae052c2c36a2fa/BOJ%231010_BuildBridge/src/Main.java

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

/**
 * BOJ#1010 다리 놓기
 * https://www.acmicpc.net/problem/1010
 */

public class Main {

    public static void main(String[] args) throws IOException {

        int T;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(br.readLine());

        while (T-- > 0) {

            StringTokenizer st = new StringTokenizer(br.readLine());

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

            if (N == M) {

                System.out.println(1);
                continue;
            }

            BigInteger num = new BigInteger("1");

            // nCr = n! / ((n-r)! * r!)
            for (int i = M; i > M - N; i--) {

                num = num.multiply(BigInteger.valueOf(i));
            }

            for (int i = N; i > 0; i--) {

                num = num.divide(BigInteger.valueOf(i));
            }

            System.out.println(num);

        }
    }
}

<동적계획법>

https://github.com/stack07142/BOJ/blob/d8bb015604a276ecd8643e16c9ae052c2c36a2fa/BOJ%231010_BuildBridge/src/Main2.java

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

/**
 * BOJ#1010 다리 놓기
 * https://www.acmicpc.net/problem/1010
 */

public class Main2 {

    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());

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

            // dp[N][M] = dp[N-1][M-1] + dp[N-1][M-2] + .. + dp[N-1][N-1]
            long[][] dp = new long[N + 1][M + 1];

            for (int i = 0; i < N + 1; i++) {

                Arrays.fill(dp[i], 0L);
            }

            for (int i = 0; i < M + 1; i++) {

                dp[1][i] = i;
            }

            if (N == M) {

                System.out.println(1);
                continue;
            }

            if (N == 1) {

                System.out.println(dp[1][M]);
                continue;
            }

            for (int i = 2; i <= N; i++) {
                for (int j = i; j <= M; j++) {
                    for (int k = i - 1; k < j; k++) {

                        dp[i][j] += dp[i - 1][k];
                    }
                }
            }

            System.out.println(dp[N][M]);
        }
    }

}