11050 이항 계수 1 (python)

백준 11050, 이항 계수 문제이다. 이항 계수가 뭔지 모르니 찾아보았다.

출처:https://velog.io/@newdana01/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98%EB%9E%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84

이항계수

이항계수란 주어진 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 개수를 의미한다.

여기서 이항이란 한 개의 아이템에 대해서 뽑거나 뽑지 않거나 두가지의 선택이 있기 때문에 붙은 단어이다.

 

이항계수의 정의는 다음과 같이 표현된다.

성질

• 2번: n개중 k를 선택하는 조합의 수는 결국 n개 중 선택받지 못한 아이템들의 조합의 수와 같다.
• 3번: 이항계수의 정의를 이용하여 3번과 같은 식을 도출해낼 수 있다.
• 4번: 파스칼의 삼각형과 관련이 깊다.

좀 더 간단한 이항계수 공식이다.

풀이

반복문을 사용해서 풀었다.

import sys

n, k = map(int, sys.stdin.readline().split())

a = 1

b = 1

# n!/(n-k)!

for i in range(n, n-k, -1):

    a *= i  # n, n-1, ..., n-k+1까지 곱셈

# k!

for j in range(1, k+1):

    b *= j  # 1부터 k까지 곱셈

# n!/((n-k)!*k!) 계산

print(a // b)  # 나눗셈 연산

 

 

하지만 풀고 나서 더 좋은 풀이가 있나 찾아보니

factorial() 함수를 사용하면 간단하게 풀 수 있다.

import sys

import math

input = sys.stdin.readline

# 입력

n, k = map(int, input().split())

# 이항계수 공식

print(math.factorial(n) // (math.factorial(k) * math.factorial(n-k)))

 

하지만 반복문을 사용해서 푼 풀이는 O(k)인 상수 시간만에 풀리는데

factorial()을 사용한 풀이는 O(n) 시간이 걸린다.