[백준] 1010번: 다리 놓기 - 파이썬/python

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

1010번: 다리 놓기

접근 방식

- dp로 푸는 경우, 메모제이션의 활용법

 

코드 풀이

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    dp = [[0]*(m+1) for _ in range(n+1)] # dp[i][j] = 좌에 i개, 우에 j개 스팟이 있을 때의 경우의 수
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if i == j:
                dp[i][j] = 1
            elif i == 1:
                dp[i][j] = j    
            else: # i < j
                dp[i][j] = dp[i][j-1] + dp[i-1][j-1] # 점화식
                
    print(dp[n][m])

사실 문제를 보는 순간 조합을 활용해 쉽게 풀 수 있다고 생각했지만, 다이나믹 프로그래밍 연습을 위해 위의 방식으로 접근했습니다. 다이나믹 프로그래밍은 메모제이션 리스트를 어떻게 구성하는지와 점화식을 어떻게 작성할지가 관건인데, 메모제이션 리스트의 경우 해당 문제에서는 좌/우 각각 n/m개의 스팟이 존재한다고 했으므로 이중 리스트 형태가 가장 활용이 용이합니다. 점화식의 경우에는 직접 초기조건 및 예외 사항을 정리하고 점화식의 관계성을 발견해 식으로 정리할 수 있습니다. 위 문제의 예외 조건은 좌, 우 스팟의 수가 일치하는 경우 그리고 초기 조건은 좌 스팟의 갯수가 1개인 경우입니다.

 

오답 이유

점화식 작성 단계에서 어려움을 겪었습니다. 이는 직접 손으로 써보며 어떤 관계성이 있는지 확인할 수 있습니다. 예를 들어 dp[3][4] = dp[3][3] + dp[2][3] = 1 + 3 = 4 입니다.