[Baekjoon] 11051_이항 계수 2

Silver I

문제(출처: https://www.acmicpc.net/problem/11051)

---

<이항 계수 2>

문제 

 

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

 

 

입력

 

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

 

 

출력 

 

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

 

 

문제 풀이

- my solution

 

import sys

if __name__=='__main__':
    n,k=map(int,sys.stdin.readline().split())

    a=1
    b=1

    # 이항 계수 = n!/k!(n-k)!
    for i in range(k+1,n+1):
        a*=i

    for i in range(1, n-k+1):
        b*=i

    print((a//b)%10007) # 10007로 나눈 나머지

 

이항 계수를 계산하는 방법은

 

n!/k!(n-k)!

 

이다.

 

위를 계산하기 위해 먼저 n!/k! 를 계산한 결과인 k+1부터 n까지의 값을 곱한다.

그다음 (n-k)! 계산을 위해 구해준 후 위에서 구한 것과 방금 구한 값을 나눠준다.

문제에서 10007로 나눈 나머지를 출력하라 했으므로 10007로 나눈 나머지를 출력해준다.

 

 

❓ 생각보다 쉬운 문제임에도 한 번만에 통과하지 못한 이유는 무엇인가?

처음에는 런타임 에러가 발생했다. OverflowError로 산술 연산의 결과가 표현하기에 너무 클 때 발생하는 에러였다.

이 문제에서 발생한 이유를 생각해보니 나눌 때 값을 하나씩 나누는 방식으로 하여 소수점이 너무 커서 발생하는 것 같다.

 

그래서 고친 방법이 n!, k!, (n-k)! 를 각자 다 곱한 후에 나누는 방법을 택하였다. 하지만 이번에는 '틀렸습니다'가 발생했다.

이번에는 /와 //의 차이 때문에 발생한 문제였다. /에서 //로 고친 후 문제를 해결할 수 있었다.

 

 

---

생각🤔

 

쉬운 문제였지만 생각보다 많은 제출을 통해 문제를 해결할 수 있었다.

 

---