[BOJ 11051] 이항 계수 2

 

11051번 (이항 계수 2)

 

 

 

Try 1) 단순히 이항 계수의 식인 nCk = n! / k!(n-k)! 을 이용하여 해결하기 

 

(idea) N과 K를 입력받았을 때, 1부터 N까지 곱하고, 그 후 1 ~ K까지 나누고, 1 ~ N-K까지 나눈다.

 

   

 하지만 이 경우, 가장 큰 범위의 정수형 타입인 

 long long 타입이라고 하더라도, N이 큰 수면

 오버플로우(Overflow)가 발생해서 정확한 수가

 저장 되지 않는다.

 

 따라서, 이 방법은 올바른 답을 도출해낼 수 없다.

 

 

 

 

 

 

 

 

 

 

Try 2) 이항 계수 공식 nCk =  n-1Ck-1 + n-1Ck 을 이용하고, Try 1)의 문제점을 해결하기 위해

(a+b)%mod = a%mod + b%mod 성질 이용하기.

 

 

(idea) 이항 계수 공식인 nCk =  n-1Ck-1 + n-1Ck 를 재귀함수를 통해서 구현하고, Try 1)에서 발생한

오버플로우 현상을 해결하기 위해서, 전체를 계산하고 한번에 10,007을 나눠주는 방식이 아니라,

10,007보다 커질 때마다 10,007로 나누어 주어 오버플로우(Overflow) 현상을 방지한다.

 

 

하지만 함수를 호출하는 시간이 오래 걸리기 때문에, 만약 N과 K가 큰 수 (ex 1000 500)로 입력이

된다면, 매우 많은 함수 호출이 필요하므로 문제 조건인 1초 이내에 수행이 끝나지 않게 된다.

 

따라서 통과하지 못한다.

 

 

 

 

Try 3) 메모이제이션 기법 이용 (https://wogud6792.tistory.com/3 참고)

 

 

 

각각의 이항계수들을 저장하는 이차원 배열(bino)을 전역 변수로 선언한다.

 

이 때, 전역변수로 저장하지 않고 main() 문 안에 지역 변수로 선언하게 되면, 지역 변수가 저장되는

메모리 공간인 stack 공간의 크기보다 이차원 배열의 크기가 더 크기 때문에 Stack Overflow

현상이 발생하게 된다.

즉, 이차원 배열(bino)을 메모리에 저장할 수 없게 되는 것이다.

 

따라서 더 큰 영역인 data영역에 저장되는 전역 변수로 선언을 해주면 된다.

 

14 ~ 15 줄에서는 파스칼의 삼각형에서 양쪽 변 위의 이항계수에 해당하는 값으로 1을 설정해주며, 

17번째 줄에서는 이전에 저장되었던 두 값을 이용해서 새로운 이항계수를 구하는 과정이다. 

 

 

따라서 다음과 같이 통과가 되었다!