[백준 1010번] 다리 놓기 (python)

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

 

기록

(dp 2일차) dp 사용해서 풀어보려고 한 번 풀고, 다른 코드보면서 조합 공식 사용하는 방법 알게되어 두 가지로 풀어봤다! 아래가 dp사용, 위가 조합 공식 사용한 결과이다.

 

코드

<dp>

from sys import stdin

def bridge(n, m):
    if n>=N : return 1
    if dp[n][m] : return dp[n][m]
    case = 0
    for i in range(m, M-N+1):
        case+=bridge(n+1, i)
    dp[n][m] = case
    return dp[n][m]

T = int(stdin.readline())
for _ in range(T):
    N, M = map(int, stdin.readline().split())
    dp = [[0]*M for _ in range(N)]
    print(bridge(0, 0))

각 n과 m이 겹치치 않도록 하는 모든 조합개수를 반환하는 재귀함수로, 각 조합마다 하위 조합들의 개수를 이차원 배열에 저장해놓는다.

 

ex) N=3, M=5라고 했을 때 탐색하는 경로

 

<조합>

import math
from sys import stdin

T = int(stdin.readline())

for _ in range(T):
    N, M = map(int, stdin.readline().split())
    bridge = math.factorial(M) // (math.factorial(N) * math.factorial(M-N))
    print(bridge

다리를 겹치지 않는 모든 (n,m)의 경우는 순서가 상관없다는 뜻이기 때문에, m개 중 n개를 조합하는 경우(mCn)와 같다.

따라서 mCn = m!//(n!*(m-n)!) 수식 사용해서 계산식을 구현한다.