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

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

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

1010번: 다리 놓기

이번 문제는 조합으로 풀면 간단하게 해결할 수 있다.

 

문제는 왼쪽의 N개의 사이트에서 오른쪽의 M개의 사이트를 결정할 때 N개의 다리가 서로 교차되지 않게 정해야 한다. 즉 M개 중에서 N개를 선택하는 조합의 문제이다. 여기서 이것이 왜 조합이냐면 M개 중에서 N개를 선택한 후 차례대로 N개의 왼쪽 사이트에 순서대로 맞춰주기만 하면 되기 때문이다.

 

그럼 이 문제는 조합을 구하는 것으로 간단하게 해결할 수 있음을 알았다. 조합의 특성 중에서 n_C_m = n_C_(m-1) + (n-1)_C_(m-1) 이라는 특징을 이용해 DP로 해결할 수 있다.

 

하지만 나는 여기서 굳이 리스트로 크게 만들지 않고 딕셔너리를 이용해서 참조했다. 이런 해시를 쉽게 사용할 수 있는 파이썬의 장점이 뿜뿜터진다.

 

아 그리고 여기서는 M이 N보다 크거나 같고, M개 중에서 N개를 고르는 것이기 때문에 때문에 위의 식 n_C_m = n_C_(m-1) + (n-1)_C_(m-1) 을 그대로 사용하는 것이 아닌 n과 m이 바뀐 m_C_n = m_C_(n-1) + (m-1)_C_(n-1) 으로 해결을 해야한다.

 

import sys

sys.setrecursionlimit(10**9)
testcase = int(sys.stdin.readline())
table = {}

def Comb(M, N):
    if (M, N) in table.keys():
        return table[(M, N)]
    if N == 0 or M == 0 or N == M:
        table[(M, N)] = 1
        return 1
    
    ans = Comb(M-1, N-1) + Comb(M-1, N)
    table[(M, N)] = ans
    return ans

for _ in range(testcase):
    N, M = map(int, sys.stdin.readline().split())
    sys.stdout.write(str(Comb(M, N)) + "\n")

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다