백준_단계별로 풀어보기_19단계_조합론

조합론 단계 (acmicpc.net)

조합론 단계

---

■ 백준 15439 베라의 패션_브론즈 4

n = int(input())
print(n**2-n)

 

■ 백준 24723 녹색거탑_브론즈 4

print(2**int(input()))

 

■ 백준 10872 팩토리얼_브론즈 5

ans = 1
for i in range(1, int(input())+1):
    ans *= i
print(ans)

 

■ 백준 11050 이항계수 1_브론즈 1 (복습)

• 이항계수 참고: https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

# def bino_coef(n, k): # 이 함수는 성능이 좋지 않음
#     if k == 0 or n == k:
#         return 1
#     return bino_coef(n-1, k) + bino_coef(n-1, k-1)

# 동적 계획법: 이미 구한 부분문제의 답을 캐쉬에 저장해서 또 구해야 할 때 바로 답을 내놓고 쓸데없는 계산을 하지 않는 것
def bino_coef(n, r):
    # 1. 먼저 캐쉬를 만든다. 2차원에, 크기는 (n+1) * (r+1) 가 된다.
    cache = [[0 for _ in range(r+1)] for _ in range(n+1)]

    # 2. 캐쉬를 초기화한다. r이 0이거나, n이 r과 같은 경우는 2.1번 성질에 따라 그냥 1이 된다.
    # 우리는 이 기초식을 이용해 다음 식을 계속해서 완성해나갈 것이다.
    for i in range(n+1):
        cache[i][0] = 1
    for i in range(r+1):
        cache[i][i] = 1

    # 3. 실제로 값을 구한다. i개의 아이템 중 j개의 아이템을 선택하는 경우의 수는 그보다 작은 두 값의 합이다.
    # 이때 for 문을 점진적으로 전진하는 것을 기억하면 된다.
    for i in range(1, n+1):
        for j in range(1, r+1):
            cache[i][j] = cache[i-1][j] + cache[i-1][j-1]
    return cache[n][r]

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

# # 고수코드: 조합 계산을 위한 정말 최소한의 계산만 하도록 구현
# n, k = map(int, input().split())
# a, b = 1, 1
# for i in range(n, n-k, -1):
#     a *= i
# for j in range(1, k+1):
#     b *= j
# print(a//b)

 

■ 백준 1010 다리 놓기_실버 5

import sys
for _ in range(int(sys.stdin.readline())):
    n, m = map(int, sys.stdin.readline().split())
    a, b = 1, 1
    for i in range(m,m-n,-1): a *= i
    for j in range(1, n+1): b *= j
    print(a//b)