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

www.acmicpc.net/problem/1010

1010번: 다리 놓기

결국 이 문제는 n,m이 주어졌을 때 mCn을 물어보는 문제이다.

그래서 순열을 풀기 위하여 두가지 방법으로 접근하였다.

 

1. 팩토리얼을 이용하기

import math

for _ in range(int(input())):
    a,b = map(int, input().split())
    c = math.factorial(b-a)
    b = math.factorial(b); a = math.factorial(a)
    print(b//(a*c))

nCr의 정의

nCr의 정의를 이용해서 문제를 풀었다.

 

2. 다이나믹프로그래밍을 이용하기

def combination(n,r):
    if dp[n][r] != 0:
        return dp[n][r]
    if r == 1:
        return n
    elif n == r:
        return 1
    else:
        dp[n][r] = combination(n-1, r) + combination(n-1, r-1)

    return dp[n][r]

if __name__ == "__main__":
    r,n = map(int, input().split())
    dp = [ [0 for _ in range(r+1)] for _ in range(n+1)]
    ans = combination(n,r)
    print(ans)

nCr의 특징

nCr의 특징을 이용하였고, 탑다운 방식을 이용하기 때문에 종료조건이 필요하다.

그래서 nC1일 때 n을 반환하고, nCn일 때 1을 반환하도록 하여서 백트래킹이 무한정 반복되지 않도록 하였다.

 

신기한 점은 100C20을 했을 때,

팩토리얼을 이용하여 풀면 0.766899824142456s가 걸린 반면, 

dp를 이용하여 풀면 2.3066134452819824s가 걸렸다.