[백준] 1010번 : 다리 놓기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1010번: 다리 놓기

 

1. 문제 설명

2. 풀이과정

해당 문제는 서쪽의 사이트가 동쪽의 사이트를 선택할 때 어차피 다리가 겹칠 수 없으므로 뽑은 결과를 나열하지는 않는다. 무조건 선택한 경우는 위에서부터 다리가 놓이기 때문이다. 따라서 조합의 경우로 계산할 수 있다.

조합을 계산하는 방법은 M개에서 N개를 선택할 때, M! / {(M - N)! * N!}으로 계산할 수 있다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. factorial() 함수를 사용하기 위해 math 모듈을 불러온다. import math
3. 테스트 케이스 개수를 입력받는다. T = int(sys.stdin.readline())
4. 테스트 케이스 횟수만큼 반복하며 for _ in range(T)
5. 서쪽과 동쪽의 사이트 개수를 입력받는다. N, M = map(int, sys.stdin.readline().split())
6. 조합의 경우의 수를 계산한다. result = math.factorial(M) // (math.factorial(M - N) * math.factorial(N))
7. 결과를 출력한다. print(result)

반응형

3. 소스코드

import sys
import math

T = int(sys.stdin.readline())
for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())
    
    result = math.factorial(M) // (math.factorial(M - N) * math.factorial(N))
    print(result)