백준 6591 파이썬 코드 답안

문제

n개의 원소 중에서 k개를 순서 없이 선택하는 방법의 수는 몇 가지 일까?

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 2^31-1 을 넘지 않는 두 자연수 n(n ≥ 1)과 k(0 ≤ k ≤n)로 이루어져 있다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 정답을 출력한다. 항상 정답이 2^31보다 작은 경우만 입력으로 주어진다.

문제풀이
고등학교 수학 문제인 조합이다. 이 조합을 계산하는 문제인데, 함정카드가 하나 있다. 바로 n의 범위가 2^31-1이라는 것이다.  이것을 계산하면 2,147,483,648이다. 대략 21억이다. 즉, 시간복잡도가 O(n)인 함수를 짠다고 하더라도 1초 내에 클리어가 안된다는 소리다. 

따라서, 이 조합은 당연스럽게도 n! / (n-k)! * k!의 공식을 그대로 구현하게 되면 필연적으로 시간초과가 발생할 수 밖에 없다. 따라서, 사람이 실제로 계산하는 방식으로 계산 횟수를 최소화 해주어야 한다. 

예를 들어 49, 6의 경우는 다음과 같이 계산할 수 있다. (49*48*47*46*45*44 / 6*5*4*3*2*1). 즉, 코드 상에서 약분할 수 있는 것은 약분하고 난 뒤에 나머지끼리만 계산을 해주면 된다. 

import sys
while 1 :
    n,k = map(int,sys.stdin.readline().split())
    if n == 0 and k == 0 :
        break
    n_k = n-k
    a = 1
    b = 1
    for i in range(n,max(k,n_k),-1) :
        a *= i
    for i in range(1,min(n_k,k)+1) :
        b *=i
    print(a//b)