파이썬 | 백준 | 1010 | 다리 놓기

 

 

solution

1. dp 이용

# 1010, 다리 놓기
import sys

t = int(sys.stdin.readline())
dp = [[0]*30 for _ in range(30)]

for i in range(30):
    for j in range(30):
        if i == 1:
            dp[i][j] = j
        else:
            if i == j:
                dp[i][j] = 1
            elif i < j:
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1]

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

29380KB

64ms

 

dp에서 문제 고른 게 아니었으면 생각 못 했을 것 같다..

---

2. 조합 이용

# 1010, 다리 놓기
import sys
t = int(sys.stdin.readline())

for i in range(t):
    n, m = map(int, sys.stdin.readline().split())
    if n == m:
        print(1)
    else:
        ans = 1
        for i in range(m, m-n, -1):
            ans *= i
        for j in range(n, 1, -1):
            ans = ans // j
        print(ans)

29380KB

64ms

 

문제 출처 www.acmicpc.net/problem/1010

1010번: 다리 놓기