[브론즈1]백준 11050번(이항 계수 1) - 코테공부 38일차(2025.03.04)

문제유형

조합

풀이 방법 도출 과정

1. 간단한 이항계수를 구하면 되는 문제.

2. 이를 위해서 itertools를 쓰면 된다. 이를 사용하여 이항계수를 구하면 간단하게 할 수 있다. 

시간 복잡도

시간 복잡도는  range(1, N +1) C K다. 최악의 경우 N이 10일 경우를 생각하면 1~10C1이라고 가정해도 1억은 넘지 않는다.

코드 및 간단설명

조합 알고리즘을 사용하였다. 

from itertools import combinations

result = []

N, K = map(int, input().split())

# range(N)로 1부터 N까지의 숫자를 iterable로 만든 후, 그로부터 K개의 조합을 구함
result.extend(combinations(range(1, N + 1), K))

print(len(result))

 

다른 풀이

1)  이항 계수 공식을 사용해서 풀은 풀이

이항계수는 C(a, b) = a!/b!(a-b)!이런 식으로 바꿀 수 있는데 이를 구현한 것이다.

a, b = map(int, input().split())
result = 1
k =  1
for i in range(a, a-b, -1):
	result *= i
for i in range(b, 0,-1):
	k*=i
print(result//k)