# 개발자 정보 (윤세형, 2011037202)
# 프로그램에 대한 설명 : 파스칼 삼각형을 그려 해당 comb(n,r) 값을 구한다.


def comb(n,r) :
  if r == 0 : # r이 0이면 1을 리턴한다.
    return 1
  elif r == n : # r이 n이면 1을 리턴한다.
    return 1
  else :
    s = [[1],[1,1]] # 삼각형 맨 처음 꼭대기를 리스트로 짜놓는다.
    def loop(a,b) :
      s2 = [1,1] # 파스칼 삼각형 한 행의 기초 틀
      if n+1 == a : # n행의 nCr을 구하기 위해서는 재귀가 n번 돌아야
        return s[n][r] # 파스칼 삼각형에서 해당 값을 인출
      while b+1 != a : # 이전 행의 0에서부터 끝까지 적용 
          s2.insert(1,s[a-1][b] + s[a-1][b+1]) # 다음 행 만들기
          b = b + 1
      s.append(s2) # 파스칼 삼각형 만들기
      return loop(a+1,0) # 돌 때마다 a는 1씩 증가, b는 초기화
    return loop(2,0) # 파스칼 삼각형 맨 꼭대기는 만들어놓았음으로 그 다음부터.


def comb1(n,r) :
  if r == 0 : # r이 0이면 1을 리턴한다.
    return 1
  if r == n :  # r이 n이면 1을 리턴한다.
    return 1
  else :
    s = [1,1] # 2번째 행까지, 1번째 행은 생략
    def loop(a,b,s) :
      s2 = [1,1] # 행을 만들기 위한 기본 틀
      if n + 1 == a : #재귀를 n번 돌린다.
        return s[r] # 원하는 행에서 r번째 있는 값을 출력한다.
      while b + 1 != a : 
        s2.insert(1,s[b] + s[b+1]) # 전의 행을 이용해 계속 다음 행을 만든다.
        b = b + 1 # 0에서부터 n까지 훝게 도와주는 변수, 돌 때마다 1씩 증가
      s = s2 # s2를 s에다 저장해준다.
      return loop(a+1,0,s) # a는 돌때마다 1씩 증가, b는 초기화, s는 메인에 전달
    return loop(2,0,s) # 구하고자 하는 곳부터 2Cn부터 만들어야하므로


def comb2(n,r) :
  if r == 0 : # r이 0이면 1을 리턴한다.
    return 1
  if r == n :  # r이 n이면 1을 리턴한다.
    return 1
  else :
    s = [1,1] # 2번째 행까지, 1번째 행은 생략
    a = 2 # 2번째까지 만들어져있음으로
    while n + 1 != a : # 재귀를 n번 돌린다.
      s2 = [1,1] # 행을 만들기 위한 기본 틀
      b = 0
      while b + 1 != a : # b + 1 = a가 되는 순간 빠져나온다.
        s2.insert(1,s[b] + s[b+1]) # 전의 행을 이용해 계속 다음 행을 만든다.
        b = b + 1 # 1씩 증가해가며 b + 1 = a가 될 때까지 삽입시킨다. 
      s = s2 # s2를 s에다 저장해준다.
      a = a + 1 # 한 번 돌때마다 1씩 증가
    return s[r] # 원하는 행에서 r번째 있는 값을 출력한다.




  
