[백준 알고리즘] 1010 다리 놓기

 다이나믹 프로그래밍 분류에 있는 다리 놓기 문제입니다.

이 문제는 두가지 방법으로 풀 수 있습니다.

조합과 다이나믹 프로그래밍 방법 두 가지로 풀 수 있는데

오늘은 조합으로 풀이를 하고 나중에 다이나믹으로 풀어보도록하겠습니다.

  문제

  해석

#1 조합

     조합으로도 문제를 풀 수 있습니다. 하지만 조합으로 문제를 풀면 int형 범위를 넘어서기 때문에 BigInteger를 사용하였습니다.

  코드

package DinamicAlgo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
 
public class Baek1010 {
 
    public void solve() {
        int T = sc.nextInt();
 
        BigInteger result;
        while (T-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            System.out.println(combination(n, m));
        }
 
    }
 
    public static BigInteger combination(int n, int m) {
        BigInteger result = new BigInteger("1");
        BigInteger divide = new BigInteger("1");
        if (m == n)
            return result;
 
        for (int i = 1; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(m));
            result = result.divide(BigInteger.valueOf(i));
            m--;
        }
 
        return result;
    }
 
    public static void main(String[] args) {
        sc.init();
 
        new Baek1010().solve();
    }
 
    static class sc {
 
        private static StringTokenizer st;
        private static BufferedReader br;
 
        static void init() {
            br = new BufferedReader(new InputStreamReader(System.in));
            st = new StringTokenizer("");
        }
 
        static String readLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            return null;
        }
 
        static String readLineReplace() {
            try {
                return br.readLine().replaceAll("\\s+", "");
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            return null;
        }
 
        static String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        static int nextInt() {
            return Integer.parseInt(next());
        }
 
        static Long nextLong() {
            return Long.parseLong(next());
        }
 
        static double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}