[Python] 백준 #1010- 다리 놓기

문제

---

1010번: 다리 놓기

코드

---

My answer

import sys
input=sys.stdin.readline

t=int(input())

for i in range(t):
    a,b=1,1
    w,e=map(int,input().split())
    for j in range(e,e-w,-1):
        a=a*j
    for j in range(w,0,-1):
        b=b*j
    print(a//b)

Another answer

from math import*
for i in range(int(input())):
    a,b=map(int,input().split())
    print(comb(b,a))

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])

풀이

---

우선 나는 dp라서 규칙을 찾다가 갑자기 이 문제 자체가 조합문제라는 것을 깨달아서 mCn을 계산해서 문제를 풀었다. 다른 사람들의 풀이를 보니 거의 다 이렇게 푸셨다. 다만 조합을 계산할 때 나는 직접 코드를 짜서 했는데 math라이브러리에 조합함수 자체가 있었다. 이번 기회에 외워야겠다. + dp로 푸신 분도 있는데 그 분의 설명을 갖고 오자면 

• 서쪽에 다리가 1개만 있을때는 , 동쪽 다리개수만 큼 지을 수 있다. ex(1,10)=10
• 서쪽 지점 동쪽지점의 개수가 똑같다면 다리는 1개 지을 수 있다.ex(3,3)=1
• 서쪽 지점갯수를 n, 동쪽지점 갯수를 m이라 하면,  (서쪽에 n개, 동쪽에 m-1개로 지을 수 있는 다리) + (서쪽에 n-1개, 동쪽에 m-1개로 지을 수 있는 다리)가 dp의 규칙이 된다.