백준 알고리즘 1010번: 다리 놓기 (Python)

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

1010번: 다리 놓기

---

문제 해결을 위한 과정

이 문제는 순서를 중요하게 생각하지 않는 '조합'의 방식으로 해결할 수 있는 문제였습니다. 동시에 팩토리얼 연산을 해야 하므로 Dynamic Programming의 방식 역시 문제 풀이의 한 요소였습니다.

팩토리얼을 우리가 흔히 아는 방식 즉 재귀적으로 구현하게 되면 한번 구한 연산을 지속적으로 반복하기 때문에 필요 없는 수많은 연산을 하게 되어 많은 컴퓨팅 리소스를 잡아먹게 됩니다. 또한 당연하게도 시간제한에 걸리게 됩니다. 따라서 이를 시간 내에 구현할 수 있게 하기 위해 피보나치수열 혹은 팩토리얼의 경우 탑다운 또는 보텀업 방식을 이용하여 해결합니다. 

문제에서 N <= M이라는 조건으로 생각해보면 결국 M개의 사이트 중에서 순서에 상관없이 N개를 뽑는 경우입니다. 가령 N이 2개이고 M이 3개일 시, 3개의 M 중에서 2개를 순서에 상관없이 뽑는 경우입니다. (예를 들면 AB, AC, BA, BC, CA, CB) 이를 염두에 두고 소스코드를 작성하면 다음과 같습니다.

---

소스코드

dp = [0] * 31
dp[0] = 1
dp[1] = 1
 
for i in range(2, 31):
  dp[i] = dp[i-1] * i
 
T = int(input())
for i in range(T):
  n, m = map(int, input().split())
  a = dp[m-n]
  b = dp[m]
  c = dp[n]
 
  print((b//a)//c)

위 소스코드에서 b//a는 mPn이고 이 결과를 c로 나눠야 mCn입니다.