[백준] 11051번 : 이항 계수 2(JAVA)

수학과 다이나믹 프로그래밍을 동시에!

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

11051번: 이항 계수 2

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 16단계

 

수학3의 카테고리에 포함되어 있으면서 동적 계획법을 이용하여 푸는 문제이다.

 

이항 계수 1의 문제는 범위가 10이였지만 이번에는 1000이다.

 

10!의 값은 3,628,800으로 수가 10만 되어도 범위가 기하 급수적으로 증가하는데

 

1000!의 값은 셀 수 없는 값이 될 것이다.

 

나는 이항 계수의 공식에 집착한 나머지 푸는데 시간이 좀 걸렸다.

 

처음에는 이항 계수의 공식으로 푼 값을 10,007로 나누어 계산했는데

 

디버깅할 때 역시나 값이 다르게 나오는 것이였다.

 

파스칼의 삼각형을 이용하며 풀면 간단하게 풀리는 문제이다.

 

Pascal's triangle

 

5C2를 구한다고 하면 4C1 + 4C2를 구해서 값을 더하면 된다.

 

4C1은 3C0 + 3C1, 4C2는 3C1 + 3C2 이렇게 점점 작은문제로 분해하여 풀 수 있다.

 

나는 2차원 배열로 선언하여 해결하였다.

 

f[i][j] = (f[i-1][j-1] + f[i-1][j]) % 10,007

 

j가 0일 경우 또는 i와 j가 같을경우에는 값이 1이된다.

 

바로 값이 나오므로 나머지 연산을 실행해도 값이 달라지지 않는다.

 

2차원 배열로 선언하여 메모리의 반만 사용하고 반은 사용하지 않는다는 단점이 있다.

 

시간날 때 메모리를 아낄 수 있는 방법도 생각해 봐야 겠다.

 

import java.util.Scanner;

public class Question_11051 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		int[][] Triangle = new int[N+1][N+1];
		
		for(int i = 0; i < Triangle.length; i++) {
			for(int j = 0; j <= i; j++) {
				if(i == j || j == 0)
					Triangle[i][j] = 1;
				else
					Triangle[i][j] = (Triangle[i-1][j-1] + Triangle[i-1][j]) % 10007;
			}
		}
		System.out.println(Triangle[N][K]);
	}
}