백준 1010번 : 다리 놓기

 문제

www.acmicpc.net/problem/1010

1010번: 다리 놓기

1010 다리 놓기

 

 구현 방법

 다리 구하는 개수는 조합을 사용하여 풀어줄 수 있습니다.

예제를 예를 들어 13 29가 입력 되었을 때 29C13을 구해주면 됩니다.

수가 너무 크므로 BigInteger 클래스로 dp 배열을 생성했습니다.

dp에 31까지의 곱셈을 구해준 다음 dp[29] / dp[M-N = 17] 를 구해주면 29부터 17까지의 곱셈을 구할 수 있습니다. 이를 dp[13]으로 나누어주면 29C13의 값이 출력됩니다.

 

 구현 코드

package BOJ.Silver;

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

public class BOJ1010_다리놓기 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int tc=0;tc<TC;tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			BigInteger[] dp = new BigInteger[31]; // 정수는 30개까지이니 31까지 선언
			dp[0] = BigInteger.valueOf(1); 
			dp[1] = BigInteger.valueOf(1); // 1C1 = 1 
			for (int i=2;i<31;i++) {
				dp[i]= dp[i-1].multiply(BigInteger.valueOf(i));
			}
		
			sb.append((dp[M].divide(dp[M-N])).divide(dp[N])+"\n");
		}
		System.out.println(sb);
	}
}

 

정답!