[백준(BOJ) / Python] 1010번: 다리 놓기

문제 링크: www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

 

문제 설명

사이트의 개수는 항상 동쪽이 많으므로 (N <= M) 다리를 지을 수 있는 경우의 수는 동쪽의 사이트를 N개 고르는 경우의 수와 같다. 즉 M개 중 N개를 뽑는 조합을 구하면 된다. 이때 이항 계수(조합의 수) 개념을 이용한다. 

 

이때 이항계수는 다음과 같은 성질이 있다. 

n개의 원소 중에서 k개의 원소를 뽑는 경우의 수는 다음 두 가지를 합한 것이다. 

1. (n - 1)개 원소 중에서 k개의 원소를 뽑고 n번째 원소를 버리기
2. (n - 1)개 원소 중에서 (k - 1)개의 원소를 뽑고 n번째 원소도 포함하기

이것을 식으로 정리한 것이 위의 수식이다. 이는 동적 계획법(Dynamic Programming)으로 구현할 수 있다. 

1. 이항 계수를 저장할 nxk 크기의 2차원 리스트(bc) 생성(또는 nxn 리스트에서 nxk만 사용)
2. 만약 bc[i][j]에서 j가 0이거나 i일 경우 이항 계수에 1 저장
3. 아닐 경우 bc[i][j] = bc[i - 1][j - 1] + bc[i- 1][j]를 이항 계수 리스트에 저장
4. i = n, j = min(i, k)까지 2~3번 반복 수행

 

 

 

소스코드

T = int(input())

while T:
    n, m = map(int, input().split())
    # Binomial Coefficient를 저장할 (m + 1)x(m + 1) 리스트 생성
    bc = [[0]*(m + 1) for i in range(m + 1)]
    
    for i in range(m + 1):
        for j in range(min(i, n) + 1):
            if j == 0 or j == i:
                bc[i][j] = 1
            else:
                bc[i][j] = bc[i-1][j-1] + bc[i-1][j]

    print(bc[m][n])

    T -= 1