2019.02.25 ~ 2019.03.31

● 2019.02.25 ~ 2019.03.31 단계별 풀어보기

    : 2019.02.25 ~ 2019.03.31 기간동안 백준 단계별 풀어보기를 진행하고 그중 '이항계수 2' 를 정리한다.

 

이항 계수 2 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

13907

5228

4150

38.458%

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)

출력

 (NK)를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

5 2

예제 출력 1 복사

10

 

 

---

● 이항계수 

   

파스칼 삼각형을 도식화 해놓은 것

참고 https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98

이항 계수 - 위키백과, 우리 모두의 백과사전

 

---

※ 파스칼의 삼각형을 참고 하였을때

         1

       1   1

     1   2   1    2는 두번째 줄의 1, 1 을 더해서 나온 결과 

    1  3   3  1  3은 세번째 줄의 1,2 // 2,1  을 더해서 나온 결과

   위와 같은 조건을 보았을때 nCk = n-1Ck + n-1Ck-1 의 조건을 구할 수 있다.

※ 문제에서 주어는 N, K 의 범위를 고려했을때 단계별로 이항계수값을 구할때 마다 10007의 나머지를 구하는

   방식으로 문제를 해결한다.

※ 중복되는 nCk 호출을 방지하여 불필요한 요소를 줄인다.

 

import java.util.Scanner;

public class Main {
	
	static int[][] arr;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		arr = new int[N+1][K+1];

		loopM(N, K);
		
		System.out.println(arr[N][K]);
	}
	
	public static int loopM(int n, int k) {
		if(arr[n][k] >= 1) {	// 이미 호출된적있는 경우 중복 계산 방지
			return arr[n][k];
		}else if(n == k || k == 0) {	// 줄단위로 첫번째와 마지막은 1로 지정
			return arr[n][k] = 1;
		}else {
			if(n-1 >= 0 && k-1 >= 0) {	// 배열의 -값을 방지
				arr[n][k] = loopM(n-1 , k-1) + loopM(n-1,k);
				arr[n][k] %= 10007;
				return arr[n][k];
			}else {
				return 0;
			}
			
		}
	}
}