[백준] 1010 다리 놓기 (파이썬), dp로 푸는 법

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

1010번: 다리 놓기

 

강 서쪽에 사이트 N개가 있고 강 동쪽에 사이트 M개가 있다고 하자. 양쪽의 사이트를 잇는 다리를 지으려고 하는데 다리가 서로 겹쳐져서는 안 된다. 이때 다리를 지을 수 있는 경우의 수는?

 

방법 1: dp

dp = [[0 for _ in range(M+1)] for _ in range(N+1)]을 만들고 dp[n][m]을 강 서쪽 사이트가 n개, 강 동쪽 사이트가 m개가 있을 때 정답이라고 하자.

dp[n][m]은 무엇일까? 일단 경우의 수를 나눠서 생각해보자. 왼쪽 사이트 맨 위를 오른쪽 사이트 맨 위에 연결시킬 수 있을 것이고(ㄱ), 오른쪽 사이트 맨 위에서 2번째 사이트에 연결시킬 수 있을 것이고(ㄴ), 오른쪽 사이트 맨 위에서 i번째 사이트에 연결시킬 수 있을 것이다(ㄷ). dp[n][m]은 이때의 정답들의 합이다.

(ㄱ)은 왼쪽 사이트 1개를 사용했고 오른쪽 사이트 1개를 사용했기 때문에 dp[n-1][m-1]이다. (ㄴ)은 왼쪽 사이트 1개를 사용했고 오른쪽 사이트 1개를 사용함과 동시에 맨 위쪽 사이트를 사용할 수 없게 만들었기 때문에 사실상 2개를 사용한 것과 동일하다. 따라서 dp[n-1][m-2]이다. (ㄷ)도 마찬가지의 논리로 dp[n-1][m-i]이다.

dp[n][m] = sum(dp[n-1][m-i] for i in range(1, m+1))

 

방법 2: dp

N=3, M=6일 때를 바탕으로 위의 풀이를 시각적으로 묘사하면 위와 같다. 그런데 잘 생각해보면

0, 0, 1, 3, 6에 해당하는 구간은 10과 동일함을 알 수 있다.

dp[n][m] = dp[n-1][m-1] + dp[n][m-1]

 

 

방법 3: 조합론

말을 살짝 다르게 표현한다면 오른쪽 사이트 M개 중 왼쪽 사이트들과 연결될 N개를 고르는 문제라고 할 수 있겠다. 사이트를 고르기만 한다면 순서는 자동으로 겹쳐지지 않게끔, 즉 오름차순으로 자동으로 정해지게 된다. 따라서 순서를 고려하지 않고 뽑으면 된다.

ans(N, M) = nCr(n=M, r=N)

풀이는 위와 같다.

한편 조합의 성질을 이용하면 방법 2와 방법 3은 동일하단 걸 보일 수도 있다. 나무위키 파스칼의 삼각형 혹은 다른 블로그의 1010번 풀이를 참고하라.

 

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())

    dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
    dp[1] = [i for i in range(M+1)]  # 초기값
    for n in range(2, N+1):
        for m in range(1, M+1):
            dp[n][m] = sum(dp[n-1][m-i] for i in range(1, m+1))

    print(dp[N][M])

방법 1을 사용한 전체 코드는 위와 같다. 설명은 안 했지만 초기값은 n=1일 때를 만들어주면 된다.