[BOJ]2591. 이항 쇼다운

문제:

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

입력:

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

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

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

출력:

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

풀이 방법:

일반적으로 nCk 를 구하는 문제와 동일하긴 하지만 n과 k의 크기가 많이 크므로 이를 정제하는 작업이 필요하다. 이전 문제에서 nCk를 구할 때 n!/k!*(n-k)!을 통해서 값을 얻는다고 하지만 실제로 사람이 계산할 때는 그렇게 하지 않는다. 10C4가 있다면 10!/4!6!을 통해서 계산을 해야겠지만 사람이라면 약분을 해서 10*9*8*7/4! 으로 구하게 된다. 따라서 이 문제도 약분을 통해서 간략화해야 한다. 또한 nCk=nCn-k와 동일하다는 공식도 존재하므로 k가 일정 값을 넘어가면 이를 통해서 k의 크기를 줄이도록 했다.

while(True):
    m,n=map(int,input().split())
    if m==0 and n==0:
        break
    if m-n<n:
        n=m-n
    answer=1
    for i in range(1,n+1):
        answer*=m
        m-=1
        answer/=i
    print(int(answer))