079 다리 놓기

첫번째 코드

 

어차피 위>아래 순으로 연결될 예정이므로,

단순히 m개 중 n개를 뽑는 경우의 수라고 생각하면 된다.

 

즉 처음에 생각한 조합의 코드를 참고하여 작성하면 된다!!

 

dp 테이블 초기화 방법 생각 잘 하기!!

- dp[i][1] = i
- dp[i][0] = 1
- dp[i][i] = 1

 

점화식 생각 잘 하기!!

 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

 

import sys
input = sys.stdin.readline

question = int(input())
dp = [[0 for _ in range(31)] for _ in range(31)]

for i in range(0, 31):
    dp[i][1] = i
    dp[i][0] = 1
    dp[i][i] = 1

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

for i in range(question):
    n, m = map(int, input().split())
    print(dp[m][n])

 

통과

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/1010.%E2%80%85%EB%8B%A4%EB%A6%AC%E2%80%85%EB%86%93%EA%B8%B0

programmers/백준/Silver/1010. 다리 놓기 at main · ornni/programmers