백준 11050번 풀이

문제

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

이항계수 내놔! 드리겠습니다! 필요없어!

 

풀이

일단 이항계수가 뭐냐...

조합론에서 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.

 

라는데요? 그래서 이거 어케구함?

 

이렇게요. 악 내눈! 이게머야! 선형대수학 들고왔어요? 아니 저거 조합임. 조합 원래 저렇게 쓰는게 맞아요.

 

사실 이거 풀이가 투트랙이라서 팩토리얼 코딩해서 조합 쓰거나 math 불러와서 comb 쓰거나 하면 된다. 나는 둘다 해서 둘다 맞았음. 팩토리얼이요? 조합이요?

# n개의 원소 중 r개를 택하는 것이 조합입니다. nCr로 표기합니다. 
def factorial(a):
    factorial = 1
    if a < 0:
        return False
    elif a == 0:
        factorial = 1
        return factorial
    elif a % 1 != 0:
        return False
    else:
        for i in range(int(a),0,-1):
            factorial *= i
        return factorial
# 아 얘는 조합 구하는데 순열이 필요해서 어쩔 수 없음. 
# nCr을 구하는 공식은 n!/r!(n-r)!입니다. 
n = int(input("n에 들어가는 수를 입력해주세요: "))
r = int(input("r에 들어가는 수를 입력해주세요: "))
bunmo = factorial(r) * factorial(n - r)
C = factorial(n)/bunmo
print("{}개의 원소들 중 {}개를 무작위로 선택하는 가짓수는 {}입니다. ".format(n,r,int(C)))

옛저녁에 순열조합도 코딩해서 깃헙에 올려뒀다.

 

조합으로 직접 계산하기

import sys

N, K = map(int,sys.stdin.readline().split(' '))

# 재귀함수의 재귀함수의 재귀함수의 재귀함수의...
def factorial(a):
    if a == 0:
        return 1
    else: 
        return a * factorial(a-1)

# nCr=n!/r!(n-r)!
bunja = factorial(N)
bunmo = factorial(K) * factorial(N - K)

print(bunja // bunmo)

팩토리얼은 재귀함수 버전인데, 위 코드랑 달리 좀 간소화됐다. 위 코드는 음수, 정수가 아닌 유리수(감마퐝숀 필요함)에 대한 처리가 같이 들어가서 좀 복잡시러운데(놀랍게도 그것도 코딩했음), 백준에서 뭐 팩토리얼 주고 음수 때려박진 않을 거 아뉴. 그래서 간소화했음.

 

그 밑에 있는 건 조합 구하는 공식이다.

 

math 불러오기

import sys
from math import comb

N, K = map(int,sys.stdin.readline().split(' '))

# math.comb(조합)
print(comb(N,K))

단 네 줄로 끝내는 방법도 있다. comb(N,K) 입력하면 nCk 바로 나옴. 공식 까먹었다 하시면 저거 쓰십쇼 저것도 맞음.