[백준 1010] 다리 놓기

문제

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

1010번: 다리 놓기

---

아이디어

동쪽(M개)의 사이트에서 서쪽(N개)의 사이트를 선택하는 문제로 간단한 조합 문제이다.

조합을 이용하면 쉽게 해결할 수 있다. 

 

아이디어 자체는 어렵지 않았고 조합을 구현할 때 factorial, combination을 직접 구현해보고, 모듈을 이용해서도 풀어봤다.

---

Solution

1. factorial을 직접 구현

def factorial(n) :
    num = 1
    for i in range(1, n+1) :
        num *= i
    return num

def combination(n, r) : 
    return int(factorial(n) / (factorial(r) * factorial(n-r)))

T = int(input())

for t in range(T) : 
    n, m = map(int, input().split())
    print(int(combination(m, n)))

 

2. math 모듈의 factorial 함수를 이용

import math

def combination(n, r) : 
    return int(math.factorial(n) / (math.factorial(r) * math.factorial(n-r)))

T = int(input())

for t in range(T) : 
    n, m = map(int, input().split())
    print(int(combination(m, n)))