[백준/Python] 1010: 다리 놓기

[백준/Python] 1010: 다리 놓기

서쪽에 n개의 다리가 있고 동쪽에 m개의 다리가 있을 때 서쪽의 다리와 동쪽의 다리를 잇는 경우의 수를 구하는 문제이다. 이때 $n<m$이다.

경우의 수는 $nCk$이고 결국은 이항계수를 구하는 문제이다. 유의할 점은 시간제한이 0.5초라 단순 반복문으로 풀기는 어렵다는 점이다.

def binomial(n, k):
    if n == k or k == 0:
        return 1
    else:
        return binomial(n-1, k) + binomial(n-1, k-1)

위 코드는 가장 간단하게 작성한 이항계수를 구하는 순환 함수이다.
$nCk=\frac{n!}{(n-k)!k!}$ 이라는 점을 이용한 것인데, 이 코드를 사용하면 당연히 시간 초과가 난다. 많은 계산이 중복되기 때문이다.

예를 들어 $5C2$를 구한다면
binomial(5, 2) = binomial(4, 2) + binomial(4, 1)이다.
그러면 binomial(4, 2) = binomial(3, 2) + binomial(3, 1)이고
binomial(4, 1) = binomial(3, 1) + binomial(3, 0)이다.

각각의 순환에서 벌써 binomial(3, 1)이 중복 계산되고 있다. 이런 오버헤드는 입력값이 증가할수록 더욱 커진다.

또 해당 문제에서 테스트 케이스는 하나만 주어지지 않는다. 예제에서만 해도 3개의 입력값이 주어지고 있다. 이미 계산한 값을 또다시 계산하는 것또한 오버헤드이다.

이런 중복 계산을 피하기 위해 동적 계획법(Dynamic programming)을 사용할 수 있다.

소스코드

---

binom = [[0 for col in range(30)] for row in range(30)]
def binomial(n, k):
    for i in range(n+1):
        for j in range(min(k+1, i+1)):
            if binom[i][j] != 0:
                continue
            if j == 0 or i == j:
                binom[i][j] = 1
            else:
                binom[i][j] = binom[i-1][j-1] + binom[i-1][j]
    return binom[n][k]
    
t = int(input())

for i in range(t):
    n, m = map(int, input().split())
    print(binomial(m, n))

DP는 bottom-up 방식이다. 순환식에서 우변의 값이 좌변의 값보다 먼저 계산되어 있다.

binomial 함수의 2번째 for문에서 min(k+1, i+1)까지만 순환하는 이유는 이항계수에선 $\binom{n}{k}=\binom{n}{n-k}$이기 때문에 모든 순환을 다 돌 필요가 없기 때문이다.

또한 binom 배열을 전역으로 선언해놓고 만약 해당 이항계수가 이미 계산되어 있다면 또다시 계산하지 않도록 했다.