백준 1010 다리 놓기(JAVA)

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

1010번: 다리 놓기

 

 

 

풀이)

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

public class Main_BJ_1010_다리놓기 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int tc=0; tc<t; tc++){
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            BigInteger[] arr = new BigInteger[31];
            arr[1] = BigInteger.ONE;
            for(int i=2; i<=30; i++){
                arr[i] = arr[i-1].multiply(BigInteger.valueOf(i));
            }
            if(n==m)
                System.out.println(1);
            else
                System.out.println(arr[m].divide(arr[n].multiply(arr[m-n])));
        }
    }
}

원래는 메모이제이션으로 조합 경우의 수를 저장하면 되는데,,,

이 문제는 간단하기 때문에 조합 공식(n! / m!(n-m)! 공식을 단순히 활용했다.

따라서,,, 팩토리얼 값만 bigInteger를 사용해서 저장해줘도....

정말 간단하게 해결할 수 있다..ㅎㅎ 야매같지만...ㅎ

 

https://st-lab.tistory.com/194

[백준] 1010번 : 다리 놓기 - JAVA [자바]

메모이제이션 참고 블로그!!