백준 알고리즘 1010 [파이썬]

배운 내용

이 문제는 문제만 봤을 때 어렵게 느낄 수도 있지만 조합에서 이항계수의 개념만 알면 쉽게 풀 수 있다.

이항계수

 

이항계수

 

 

 

문제 

문제풀이

이항계수가 n개의 원소에서 k개의 부분집합을 고르는 경우인 것처럼, 이 문제에서 N개의 장소들을 어느 M개의 장소들에 연결해야할지 정하는것도 이항계수라고 볼 수 있다. 그래서 이항계수의 공식을 사용해야하는것을 이해하는게 이 문제의 키 포인트인것 같다.

# 조합을 이용해서 문제를 풀어야한다.
from sys import stdin
read = stdin.readline
for _ in range(int(read())):
  N, M = map(int, read().split())
  num_n = 1
  num_m = 1
  num_d = 1
  for i in range(1, N+1):
    num_n *= i
  for j in range(1, M+1):
    num_m *= j
  for x in range(1, M-N+1):
    num_d *= x
  # 큰 숫자들을 나눌때는 '/'하면 안되고 '//'를 해야한다.
  print(int((num_m//num_n)//num_d))