[Baekjoon] 백준 알고리즘: 1010 - 다리놓기

문제

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

1010번: 다리 놓기

내가 생각했던 풀이과정

 

1) 순서가 없는 조합 문제이다. 조합이란 집합에서 서로 다른 n개의 원소 중에서 순서와 상관없이 r개를 선택하는 것이다.

순서가 없다고 생각한 이유는 어떤 다리를 놓아도, 순서에는 영향을 미치지 않기 때문이다. 

2) m이 n보다 크기 때문에 최대 연결할 수 있는 다리의 갯수는 n개이다.

m개의 지역에 n개의 다리를 놓을 수 있는 경우를 찾는 것이기 때문에 mCn 문제이다.

 

조합론: https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9

 

조합 - 위키백과, 우리 모두의 백과사전

조합이기 때문에 팩토리얼을 이용하였고, 이를 이용해 mCn 을 구현하였다

나의 풀이

testcase = int(input())

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

for j in range(testcase):
    n, m = map(int, input().split())
    bridge = factorial(m) // (factorial(n) * factorial(m - n))
    print(bridge)

다른 사람의 풀이

import math
T=int(input())
for i in range(T):
    n,m = map(int,input().split())   

    answer=math.factorial(m)//(math.factorial(n)*math.factorial(m-n))
    print(answer)

math 모듈을 이용하여서 팩토리얼을 이용하였고 풀이 나머지는 같다.

새로 알게된 점, 확인해야할 점

순서가 있는 문제는 순열

순서가 없는 문제는 조합