[algorithm] 백준 1010 - 다리 놓기

[algorithm] 백준 1010 - 다리 놓기

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 1010번 문제 - 다리 놓기 의 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 1010

 

백준 1010번 다리 놓기 문제 보러가기

 

반응형

 

문제 해석

 

사이에 강을 두고 왼쪽 오른쪽 사이트에 다리를 놓는 경우의 수를 구하는 문제입니다.

문제에 서로 겹치지 않는다라는 말이 등장하는데요. 이 뜻은 같은 사이트에 연결된 다리가 있으면 안된다는 말로

이미 다른 사이트와 연결되어있는 경우에는 다리를 더이상 놓을 수 없다는 말입니다.

힌트 : C가 생각나실 것 같습니다.

 

풀이

 

# 1010 다리 놓기
from math import factorial

T = int(input())

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

 

풀이 해석 및 팁

 

우리가 떠올려야하는 것은 바로 C(조합)입니다.

mCn 이 문제에서 원하는 조합의 결과인데요.

강 오른쪽에 존재하는 사이트가 m개 왼쪽에 존재하는 사이트가 n개 이므로

m개 중에 n개를 선택하는 경우의 수를 의미하게됩니다.

큰 어려움 없이 조합을 이용해 쉽게 풀이가 가능했습니다. 

---

여기까지 백준 1010번 다리 놓기 문제 풀이였습니다.

이번 문제의 정답률은 48% 정도입니다.

조합 공식을 이용하면 큰 어려움 없이 바로 해결이 가능한 문제였습니다.

궁금한 점이 있으시다면 댓글로 남겨주세요.

감사합니다.