[알고리즘][Python] 백준(BOJ) 1010 다리 놓기_파이썬

 

조합

1010 다리 놓기    https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

 

문제 풀기 전 공부할 것 : 수학, 다이내믹 프로그래밍, 조합론

 

 

 

 

 

 

 

풀이 1

<내용>

• 다리를 지을 때 겹칠 수 없기 때문에 규칙을 찾아보면
• 서쪽에 1개, 동쪽에 n개 있을 때 다리는 n개 지을 수 있다.
• 서쪽의 사이트 개수와 동쪽의 사이트 개수가 똑같다면 다리는 1개 지을 수 있다.
• 서쪽의 사이트 개수가 n, 동쪽의 사이트 개수가 m이라면 (서쪽에 n개, 동쪽에 m-1개로 지을 수 있는 다리) + (서쪽에 n-1개, 동쪽에 m-1개로 지을 수 있는 다리)와 같다.
• 위의 규칙에 맞게 프로그램을 구현하면 된다.

 

 

<코드>

import sys
input = sys.stdin.readline

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)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if i == 1:
                dp[i][j] = j
                continue
            if i == j:
                dp[i][j] = 1
            else:
                if j > i:
                    dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
    
    print(dp[n][m])

 

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 조합을 이용해서 해결할 수 있다.
• 조합 계산을 위한 factorial을 정의하고 조합을 이용하여 다리의 개수를 구한다.

 

 

<코드>

import sys
input = sys.stdin.readline

def factorial(n):
    f = 1
    for i in range(n):
        f *= (i+1)
    return f

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    print(factorial(m) // (factorial(n) * factorial(m-n)))