백준 [단계별로 풀어보기]: (19단계) "조합론", python

백준 [단계별로 풀어보기]: (19단계) "조합론", python

 

1. 문제번호 및 정답비율

19단계 조합론 : 문제번호 및 정답비율

2. 문제별 필요 지식 및 풀이 포인트

# 1. 15439 베라의 패션

n*(n-1)

# 2. 24723 녹색거탑

2**n

# 3. 10872 팩토리얼

def factorial(n): if n<=1:return 1; return n*factorial(n-1)

 

# 4. 11050 이항 계수 1

nCr = n! / (n-r)!r!

# 5. 1010 다리 놓기 / 다시풀기

규칙성 찾는게 어려움

3. 문제별 풀이 코드

# 1. 15439 베라의 패션
# 상의와 하의가 서로 다른 색상인 조합의 가짓수를 출력한다.
#from itertools import combinations #필요없네..?
n = int(input())
print(n*(n-1))


# 2. 24723 녹색거탑
# 측면의 개수 = 바닥으로 내려오는 경우의 수 = 2**윗면의개수
n = int(input())
print(2**n)


# 3. 10872 팩토리얼
n = int(input())
def factorial(n):
    if n <= 1: return 1
    return n*factorial(n-1)
print(factorial(n))


# 4. 11050 이항 계수 1
# 이항계수 = 조합의 가짓수
def factorial(m):
    cnt = 1
    for i in range(1,m+1):
        cnt *= i
    return cnt
n,k = map(int, input().split())
l = factorial(n-k) #n,k보다 윗줄에 선언해야 된다.
n = factorial(n)
k = factorial(k)
print(int(n/(k*l)))
'''math라이브러리 활용'''
import math
n,k = map(int, input().split())
print(int(math.factorial(n)/(math.factorial(k)*math.factorial(n-k))))


# 5. 1010 다리 놓기 / 다시풀기
''' 3 5
3C1 2C1 1C1 = 3 2 1 = 6
5P3 = 5!/2! '''
n, m = map(int, input().split()) # n < m
#횟수: (m-n-1)
#경우의수: k=n~m, n-1Ck-1

def fa(x):
    cnt = 1
    for i in range(1,x+1):
        cnt *= i
    return cnt
comb = 0
for k in range(n,m+1):
    comb += fa(n-1)/(fa(n-k)*fa(k-1))
print(comb)