[Baekjoon][Python] 1010번 다리 놓기

1010번 다리 놓기

문제

풀이

생각보다 간단한 문제인데, 중간에 실수를 하나해서 골치아팠던 문제이다. 문제를 잘 읽어보면 조합을 이용해 간단히 해결할 수 있는 것을 알 수 있다. 하지만 DP를 학습하고자 DP를 통한 풀이를 진행했다.

이차원 배열을 그려 살펴보면, 어떤 값 [a][b]의 값은 [해당 열의 시작:a-1][b-1]들의 합임을 알 수 있다.

이를 구현한 코드는 아래와 같다.

import sys
input = sys.stdin.readline

# 테스트 케이스 수
T = int(input())

for _ in range(T):
    N, M = map(int, input().split())
    if N == M:
        print(1)
    else:
        arr = [0]
        for i in range(M):
            arr.append(i + 1)
        for i in range(2, N + 1):
            new_arr = []
            for j in range(i, M + 1):
                new_arr.append(sum(arr[i - 1:j]))
            arr[i:] = new_arr
        print(arr[-1])

또는 간단하게 조합을 통한 풀이는 다믕과 같다.

from math import factorial
import sys
input = sys.stdin.readline

N = int(input())
for _ in range(N):
    N, M = map(int, input().split())
    print(factorial(M) // (factorial(M-N) * factorial(N)))

결론

이제 DP 문제는 어느정도 익숙해진 것 같아 조금 고난도의 문제도 도전해봐야겠다.