[Python Algorithm] 다리 놓기 BOJ #1010

문제

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

내 문제 풀이

import sys

t = int(sys.stdin.readline().strip())
dp = [[0 for _ in range(31)] for _ in range(31)]
for i in range(1, 31):
    for j in range(1, 31):
        if i == 1:
            dp[i][j] = j
        elif i == j:
            dp[i][j] = 1
        elif i < j:
            dp[i][j] = dp[i-1][j-1] + dp[i][j-1]

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

👉 DP/수학/조합 문제이고, 나는 DP로 구현했다.

다리를 놓을 수 있는 경우의 수를 위의 그림으로 표현했고,

그 경우의 수는 아래와 같은 규칙을 갖는 것을 알 수 있다.

1. n이 1일 경우에는 m
2. n이 m과 같은 경우에는 1
3. n이 m보다 작은 경우에는 dp[n-1][m-1] + dp[n][m-1]

 

+ 나는 이렇게 dp를 이용하여 풀이했지만,

조합을 이용하면 쉽게 풀 수 있다고 한다,,!

< 다른 풀이 참고 사이트 >

• https://yoonsang-it.tistory.com/33
• https://velog.io/@johnberman-j/%EB%B0%B1%EC%A4%80-1010%EB%B2%88-%EB%8B%A4%EB%A6%AC-%EB%86%93%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

 

💡 피드백

난이도가 낮은 문제로 나와있지만,,

조합을 사용해서 풀이하는 문제를 처음 접해보는 것 같아서 이렇게 글을 남겨놓는다.

조합론도 공부해두면 문제 풀이할 때 편할 수 있을 것 같다.