[백준] 다리 놓기

문제보기 - https://www.acmicpc.net/problem/1010

문제명    - 다리놓기

난이도    - S5

문제유형 - DP

풀이일자 - 25.03.13

 

📌 문제 탐색하기

 

• 강의 서쪽과 동쪽에 사이트가 있고 다리를 놓아야 함
  • 다리는 겹치지 않아야 하며 한쪽 사이트당 하나의 다리만 연결할 수 있음
• N개의 서쪽 사이트와 M개의 동쪽 사이트가 주어질 때 다리를 놓는 경우의 수를 출력해야 함

 

🛠 시간복잡도 확인

• 내장 함수 math.comb() 활용 -> O(N)

 

📌 코드 설계하기

1. 테스트 케이스 개수 T 입력받기
   • sys.stdin.readline()
2. N, M 입력받고 내장 함수 활용하여 출력하기
   • print(math.comb(M, N))

 

📌 정답 코드(1회차)

import sys
import math

# 1. 테스트 케이스 개수 T 입력받기
T = int(sys.stdin.readline().strip())

# 2. N, M 입력받고 내장 함수 활용하여 출력하기
for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())
    print(math.comb(M, N))