[BAEKJOON] 11051번 이항 계수 2

문 제

 

소 스  코 드

#include<iostream>

constexpr int MAX_SIZE{ 1'000 };
int nCk(int n, int k);

int main() {
	int N, K;

	std::cin >> N >> K;

	std::cout << nCk (N, K);

	return 0;
}

int nCk(int n, int k) {
	static int arr[MAX_SIZE][MAX_SIZE];
	if (arr[n][k] > 0) return arr[n][k] % 10'007;
	else if (k == 0 || k == n) return arr[n][k] = 1;
	else return arr[n][k] = (nCk(n - 1, k - 1) + nCk(n - 1, k)) % 10'007;
	
}

 

풀 이

 

• 이항 계수 1

초보의 코딩 공부

이항 계수 1번과 같은 방법으로 푼다면 범위가 크기 때문에 문제가 발생할 수 있다.
만약 배열의 내부에 변경이 있다면 빠르게 넘어갈 수 있도록
메모이제이션(Memoization) 방법을 사용하여 구현을 해야한다.

만약, { N : 5, K : 2 }일 때, 함수가 시작하자 마자 변화한 값을 보여주는 그래프 이다.

13번의 1 2 3 4를 더한 10의 결과가 나온다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] : https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2