[모각코] 220820 Today I Learned

<백준 1010번 - 다리 놓기>

 

그렇게 안 어려워보여서 선택한 문제인데

풀이 방법을 생각하다보니 dp.....? 라는 생각이 들어서 슬펐다. (오래 걸리기 때문)

 

문제 보자마자 어떤 알고리즘을 사용해야 하는지 감이 잡혔으면 좋겠다.

 

 

조금 더 자세한 풀이는

2022.08.20 - [Coding/백준] - [Python] 백준 1010번 - 다리 놓기

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

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    dp = [[1 for _ in range(m)] for _ in range(n)]

    for i in range(n):
        for j in range(i, m):
            if i == 0:
                dp[i][j] = j+1
                continue
            if i == j:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
                
    print(dp[-1][-1])

 

남은 방학에는 현재 진행중인 것들을 마무리 해야 해서

개강 후 부터 알고리즘 문제를 좀 더 집중적으로 풀 생각인데, 그때 제일 먼저 dp를 연습해야겠다.