[Python] 백준 알고리즘 1010번 : 다리 놓기

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

1010번: 다리 놓기

 

 

 

 

 

👩‍💻문제 이해

1. 한 사이트는 최대 한 사이트에만 연결 될 수 있으므로 -> 중복불가!

 

M(동쪽 사이트)개의 다리 중 N(서쪽 사이트)개의 다리를 선택하는 경우의 수를 구하면 된다.

 

2. 서로 다른 다리들은 서로 겹쳐질 수 없다!

-> ex) (1,2,3,4,5) 5개의 다리들 중 (1,2,4)번 3개의 다리들만 연결 되는 경우를 생각해보면

(1,2,4)의 순서로 연결되던 (1,4,2) 또는 (2,1,4)의 순서로 연결되던

겹치지 않고 연결될 수 있는 경우는 (1,2,4) 하나이기 때문에 순서를 고려하지 않는 조합공식을 사용해주면 된다!

 

 

 

👩‍💻math 모듈의 comb 함수를 사용한 코드 : 성공🌈

import math
n = int(input())
for i in range(n):
  a, b = map(int,input().split())
  print(math.comb(b,a))
  
# math 모듈의 comb함수를 사용하면 조합의 수를 쉽게 구할 수 있다.

 

 

👩‍💻조합 공식과 팩토리얼 구하는 함수 사용 : 성공🌈

def factorial(n):
  res = 1
  for i in range(1,n+1):
    res *= i
  return res
# 팩토리얼 수 구하는 함수 정의

n = int(input())
for i in range(n):
  n, m = map(int,input().split())
  case = factorial(m) // (factorial(n) * factorial(m - n))
  print(case)
# 조합공식 사용한 결과값 출력

 

 

🚀결과🚀

 

 

 

✨Point✨

<조합 구하는 방법>
1. math.comb 사용
2. 팩토리얼 구하는 함수 + 조합 공식 이용