백준 - 다리놓기 (Dynamic Programming) / Silver 5 / 1010번

문제 📋

백준 삼성기출 - 다리 놓기

풀이 📝

import sys
from math import factorial


n = int(sys.stdin.readline())
testcase = [map(int, sys.stdin.readline().split()) for _ in range(n)]

for N, M in testcase:
    print(factorial(M) // (factorial(M-N) * factorial(N)))

다리가 겹치지 않기 때문에 M개의 사이트에서 N개를 선택하는 mCn이 해당 문제의 답이다.
mCn은 M! / {(M-N)! * N!}로 쉽게 계산할 수 있다.

근데 한가지 짚고 넘어갈게 있다.
이 문제는 왜 DP로 분류되어 있을까?

그것은 mCn은 이항계수의 성질에 따라
mCn = m-1Cn-1 + m-1Cn 으로 분리 시킬 수 있다.

해당식의 의미는 임의의 i번째 원소에 대하여 해당 원소를 반드시 포함하는 경우의 수 와
반드시 포함하지 않는 경우의 수를 합하면 전체 경우의 수라는 것이다.

말이 어려운데 쉽게 말하면 전체 경우의 수 중에서 그냥 특정 원소 포함하는 경우랑 포함 안하는 경우랑 분리한 것 이다.

해당식을 다음과 같이 2차원 dp배열로서 점화식으로 표현할 수 있고
그렇게 하면 DP를 이용해 문제를 풀 수 있다.

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

그러나 개인적인 생각으로 DP 문제는 DP 배열에 의미를 부여하여 정의하기도 어렵다.
근데 해당식을 조합으로부터 생각해서 찾아내는 것이 아니라
문제 속에서 의미를 파악해서 찾기란 매우 어렵다고 생각한다.

따라서 실전에서는 조합으로 풀고 빠르게 넘어가는 것이 맞다고 생각한다.