Baekjoon11051: 이항 계수2

이항 계수 2

1 초

256 MB

33293

12522

9832

38.451%

풀이

팩토리얼을 메소드를 만들고 숫자 데이터를 Double로 받아 연산해도 결과값은 NaN이 나온다. 1000까지 곱하기 때문에 Double의 표현 자리수를 넘어가는데 이를 방지하기 위해 중간중간 곱하기마다 10007로 나누어 숫자 크기를 줄여주어야 한다(모듈러 연산).

파스칼의 삼각형

처배열을 이용한 풀이를 생각했지만 파스칼의 삼각형 풀이보다 효율적이지 못한 것 같다.

이항 계수의 성질과 dp를 이용하면 빠르게 풀이할 수 있다.

(N K)=(N-1 K-1) + (N-1 K)

N을 1000까지 사용하므로 [1001][1001] 배열을 만들고 dp를 적용한다.

K=0일 때와 N=K일 때 dp의 값은 1이다.

import java.util.*;
public class Main {
	static int[][] dp= new int[1001][1001];
	static int Pascal(int N, int K) {
		if(dp[N][K]==0) {
			if(K==0 || N==K) { //양사이드의 dp의 값은 1
				dp[N][K]=1;
			}else { //사이드가 아니라면 이전항의 두개를 더한 값이다
				dp[N][K]=(Pascal(N-1,K)+Pascal(N-1,K-1))%10007;
                //10007로 중간중간마다 나누어주는 모듈러 연산을 수행한다
			}
		}
		return dp[N][K];
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt(),K=sc.nextInt();
		System.out.print(Pascal(N,K));
}}