[백준] 16단계: 조합론

1. [15439] 베라의 패션

베라는 상의 N 벌과 하의 N 벌이 있다. i 번째 상의와 i 번째 하의는 모두 색상 i를 가진다. N 개의 색상은 모두 서로 다르다. 상의와 하의가 서로 다른 색상인 조합은 총 몇 가지일까?

N = int(input())
print(N*(N-1))

2. [24723] 녹색거탑

Naver D2를 아시나요? D2는 For Developers, By Developers의 약자로, 개발자들을 위해 개발자들이 직접 만들어 가고 있는 네이버 개발자 지원 프로그램입니다. 네이버가 축적한 기술과 지식을 공유하고, 외부 개발자들을 지원해 대한민국 개발자 역량 강화를 이끌고, 이를 통해 업계 전체와 네이버가 함께 성장하는 선순환 구조를 만들고자 합니다.

사실 네이버의 개발자 지원은 오랜 기간 꾸준히 이어져 왔습니다. 개발자 컨퍼런스 DEVIEW를 비롯, 오픈 소스와 개발 도구 공개, 학회 및 커뮤니티 지원 등 여러 지원 프로그램이 있었습니다. 이런 다양한 프로그램을 하나로 통합한 것이 바로 Naver D2입니다.

2022년 봄 어느 날.

전 세계에 코딩괴물이 나타났다.

그리고 코딩괴물과 함께 갑작스레 등장한 '그것'...

바로 녹색거탑이다.

녹색거탑의 정상에서는 매년 NAVER가 개최하는 개발자 컨퍼런스 DEVIEW가 열린다. 이 DEVIEW에 참여하면, 코딩에 깊은 깨달음을 얻어 코딩괴물이 될 수 있다고 전해진다. 그리고 코딩괴물은 녹색거탑의 정상에서 내려온다. 예전부터 전해 내려오는 D2 비전서에 의하면, 코딩괴물이 녹색거탑의 정상에서 내려오는 경우의 수를 파악한 사람은, 개발자 컨퍼런스 DEVIEW에 참여할 수 있다 한다. 그리고 DEVIEW에 참여해 본인도 코딩괴물이 될 수 있다!

 

녹색거탑은 위 그림과 같이 규칙적으로 쌓여있다.

• 그림의 시야에 보이지 않는 블록은 없다.
• 그림의 시야에 보이는 블록의 윗면만 이용해 녹색거탑을 내려올 수 있다.
• 녹색거탑이 N층이면, 총 N개의 블록을 이용한 최단 경로로만 내려온다.
• 녹색거탑을 내려올 때는 정상에서 시작해 노란색 바닥까지, 항상 인접한 아래층의 블록으로만 내려온다.

녹색거탑을 정복하고 DEVIEW에 참여하자.

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

3. [10872] 팩토리얼

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

n = int(input())
num = 1
if n == 0:
    pass
else:
    for i in range(n, 0, -1):
        num *= i
print(num)

4. [11050] 이항 계수 1

자연수 N과 정수 K가 주어졌을 때 이항 계수 (binom{N}{K})를 구하는 프로그램을 작성하시오.

def factorial(n):
    num = 1
    if n != 0:
        for i in range(n, 0, -1):
            num *= i
    return num

N, K = map(int, input().split())
print(int(factorial(N)/(factorial(K)*factorial(N-K))))

5. [1010] 다리 놓기

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

def factorial(n):
    num = 1
    if n != 0:
        for i in range(n, 0, -1):
            num *= i
    return num

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    print(int(factorial(M)/(factorial(N)*factorial(M-N))))