[BOJ] 11048: 이동하기 (Python)

문제 링크

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

풀이 전략

Dynamic Programming

2차원의 배열 dp 를 선언하고, top-down 방식으로 동적계획법을 시행한다.
준규가 움직일 수 있는 방법은 현재 위치가 $(r, c)$일 때, $(r+1, c), (r, c+1), (r+1, c+1)$ 세 가지이므로, 다음과 같은 세 경우 중 최대를 구하면 된다.

1. dp[j-1][i]+ maze[j][i]

2. dp[j][i-1]+ maze[j][i]

3. dp[j-1][i-1] + maze[j][i]

구현

if __name__ == "__main__":
    n, m = map(int, input().split())
    maze = []
    for _ in range(n):
        maze.append(list(map(int, input().split())))
        
    # memoization을 위한 list
    dp = [[0]*(m+1) for _ in range(n+1)]
	
    for j in range(1, n+1):
        for i in range(1, m+1):
            # 세 경우 중 최대 구하기
            dp[j][i] = max(dp[j-1][i], dp[j][i-1], dp[j-1][i-1]) + maze[j-1][i-1]

    print(dp[n][m])

복잡도

• Basic Operator: max
• Time Complexity: $O(n)$