[백준 11050 파이썬] 이항 계수 1 (브론즈1, 조합론)

알고리즘 유형 : 조합론
풀이 참고 없이 스스로 풀었나요? : O (풀이 참고 후 다른 풀이 시도)

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

SOLVE 1

팩토리얼을 반복문 돌면서 구하는 풀이

import sys
input = sys.stdin.readline

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

result = 1
for i in range(K):
    result *= N
    N -= 1

divisor = 1
for i in range(2, K+1):
    divisor *= i

print(result // divisor)

SOLVE 2

팩토리얼 재귀 함수를 정의해서 푸는 문제

import sys
input = sys.stdin.readline

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

def factorial(n):
  if n == 0 or n == 1:
    return 1
  else:
    return n * factorial(n-1)

# 조합 공식 nCk = n!/(n-k)!k!
print(factorial(N) // (factorial(N-K) * factorial(K)))

SOLVE 1) 풀이 요약 (팩토리얼을 반복문 돌면서 구하는 풀이)

1. 조합 공식 풀이보다 코드가 복잡하지만 시간복잡도가 빠름

2. 조합 공식 대신에, nCk = n*(n-1)(n-2)... / k! (분자의 곱셈에서 수의 개수는 k개임) 를 사용했다.

SOLVE 2) 풀이 요약 (팩토리얼 재귀 함수를 정의해서 푸는 문제)

1. 조합 공식 nCk = n!/(n-k)!k!로 풀기. 팩토리얼 값을 구해주는 재귀 함수 정의

배운 점, 어려웠던 점

1. K+1 길이의 리스트 "DP"를 할당한다. 인덱스가 곧 액수를 의미한다.

2. 조합 공식 nCk = n!/(n-k)!k! 가 가물가물해서 바로 못 떠올려서 1번 풀이처럼 풀었던 것 같다.