[Python]백준 #11050 이항계수1(class2+)

https://www.acmicpc.net/problem/11050

11050번: 이항 계수 1

✔ 알고리즘

• 수학
• 구현
• 조합론

✔ 접근방법

1.

이항계수의 분자 : N부터 1씩 뺀 숫자를 K개 곱함 , 분모 : K부터 1씩 뺀 숫자를 K개 곱함

반복문으로 K번 반복하며 숫자에 -1를 반영해주려고 함

처음에는 분자, 분모를 각각 곱해주고 마지막에 나눠주는 것이 아니라

result *= ((N-i)/(K-i)) 형태로 그때그때 값을 나눠준 값을 곱해주려고 했다 ex) 5C3 = (5/3) * (4/2) * (3/1)

그런데 이렇게 했더니 자꾸 틀려서 값을 여러개 찍어봤더니 딱 나눠 떨어지는 결과가 이런 연산을 하면 이상하게 나옴

=> 분자, 분모를 각각 곱해 계산하고 마지막에 나눠줌

 

💡문제에서 요구하는 출력 형태는 정수 이므로 마지막 결과도 정수형으로 출력해줘야 정답으로 간주

✔  코드

N, K = map(int, input().split())
p,s = 1,1
for i in range(K):
    p*=(N-i)
    s*=(K-i)
print(int(p/s))

✔ 배운점/아쉬운점

1. math 라이브러리의 팩토리얼 함수나, 재귀함수로 직접 구현하는 방법도 있음

(난 함수 호출을 여러번 하는 것이 더 부담스러울 것 같아서 사용X)

2. 계산 순서나 마지막 출력 형태도 꽤 중요하다는 것을 배움