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

[문제]

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

1010번: 다리 놓기

[풀이]

 

우선 이 문제는 풀이 방식이 두 가지가 있다.

1. 동적 프로그래밍을 이용해 풀기
2. 조합을 이용해 풀기

 

동적 프로그래밍 풀이

	1	2	3	4	5
1	1	2	3	4	5
2	X	1	3	6	10
3	X	X	1	4	10

행이 n, 열이 m을 나타낼 때 

1. n이 1인 경우 만들어지는 경우의 수는 m과 같다.

2. n이 2이상인 경우 num[n][m] = num[n][m - 1] + num[n - 1][m - 1] 의규칙을 발견할 수 있다.

 

입력이 최대 30이기 때문에 해당 규칙을 토대로 리스트를 31까지 만들고 입력받은 n과 m에 대하여 dp[n][m] 을 출력한다.

 

 

[동적 프로그래밍 코드]

import sys

dp = [[1] * 31 for _ in range(31)]

for i in range(31):
    dp[1][i] = i
for i in range(2, 31):
    for j in range(i + 1, 31):
        dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]

for _ in range(int(sys.stdin.readline())):
    n, m = map(int, sys.stdin.readline().split())
    print(dp[n][m])

 

조합 풀이

https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9

조합 - 위키백과, 우리 모두의 백과사전

n <= m 이기 때문에 최대로 연결할 수 있는 다리의 개수는 n개이다.

m개의 지역에 n개의 다리를 놓는 경우의 수는 mCn 으로 표현할 수 있고 이는 m! / (m-n)!n! 이다.

 

따라서 팩토리얼을 계산하는 함수를 구현하면 문제를 해결할 수 있다.

 

 

[조합 코드]

import sys


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


for _ in range(int(sys.stdin.readline())):
    n, m = map(int, sys.stdin.readline().split())
    bridge = factorial(m) // (factorial(n) * factorial(m - n))
    print(bridge)