[python] 조합(nCr) 반복문과 재귀 호출을 통해 구하기

문제 설명

n개 중에서 r개를 선택할 때의 경우의 수를 구하는 문제다.

https://terms.naver.com/entry.naver?docId=3350149&cid=60210&categoryId=60210

조합 공식

코드

def combi(n, r):
  i = 1
  p = 1
  while i <= r :
    p = p*(n-i+1) // i
    i += 1
  return p

n = 0
while n <= 5:
  r = 0
  while r <= n:
    print("{0}C{1} = {2}".format(n,r,combi(n,r)))
    r += 1
  n += 1

다른 풀이

f(n,r) 을 n개 중에서 r개를 선택하는 경우의 수라고 정의하면 같은 함수로 정의가 된다
f(n,r) = 마지막 물건은 고른 경우의 수 + 마지막 물건을 고르지 않은 경우의 수
(물건을 고르는 경우의 수는 "해당 물건을 고른 경우"와 "해당 물건을 고르지 않은 경우"로 나눌 수 있으므로 위의 수식도 성립한다.)
예시) 3C2 (O을 고른 경우 X를 안 고른 경우)
(1) OOX (2) OXO (3) XOO 
[1] 세 번째 공을 선택하지 않은 경우 (1) OOX ( 남은 2개의 공에서 2개를 선택하는 경우다) 1개
[2] 세 번째 공을 선택한 경우 (2)OXO (3)XOO ( 세 번째 공을 선택했기에 남은 2개의 공 중에서 한 개를 선택한다) 2개
따라서, f(n,r) = f(n-1, r) + f(n-1,r-1)

코드

def combi(n,r):
  if r == 0 or r == n :
    return 1
  else:
    return combi(n-1,r) + combi(n-1, r-1)

a, b = map(int, input("공의 개수와 선택할 수를 입력하시오 :").split())
print(combi(a,b))

해설

r==0 이면 1개도 선택하지 않는 다는 뜻이므로 선택하는 개수는 1 / r==n이면 총 개수와 뽑는 개수가 같으므로 이 또한 선택하는 개수는 1이다.

combi(n-1,r) + combi(n-1,r-1) 을 반복하며 nCr의 경우의 수를 구한다.
예시) 3C2
combi(n-1,r) -> combi(2,2) return 1
combi(n-1,r-1) -> combi(2,1) -> def combi() 다시 넣기 (재귀호출) -> combi(1,1) + combi(1,0) 둘다 return 1