[백준] 2169번 : 로봇 조종하기

2169번: 로봇 조종하기

🤔 문제분석

이 유형 또한 다이나믹 프로그래밍 응용 문제로, 왼쪽, 오른쪽, 아래쪽으로만 이동 할 수 있는 것을 잘 분석하여 문제를 해결하는 것이 Key Point 이다.

맨위의 행에서는 오른쪽으로만 이동 할 수 밖에 없다, 그 이후의 행에서는 위에서 온경우, 오른쪽에서 온경우, 왼쪽에서 온경우 모두 다 따져봐야한다. 각각의 왼쪽, 오른쪽, 위쪽에서의 값은 항상 최대값을 갖게 만들어야한다.

💻 코드

import sys
INF = -int(1e10)
input = sys.stdin.readline

N, M = map(int, input().split())

table = [list(map(int, input().split())) for _ in range(N)]

dp = [[INF for _ in range(M)] for _ in range(N)]
dp[0][0] = table[0][0]

for i in range(1, M):
    dp[0][i] = dp[0][i-1] + table[0][i]

for i in range(1, N):
    left = [0 for _ in range(M)]
    left[0] = table[i][0] + dp[i-1][0]
    
    right = [0 for _ in range(M)]
    right[M-1] = table[i][M-1] + dp[i-1][M-1]
    for j in range(1, M):
        left[j] = max(left[j-1] + table[i][j], dp[i-1][j] + table[i][j])
        right[M-j-1] = max(right[M-j] + table[i][M-j-1], dp[i-1][M-j-1] + table[i][M-j-1])
    
    for k in range(M):
        dp[i][k] = max(left[k], right[k])    

print(dp[N-1][M-1])

🎯 피드백 및 개선사항

처음에는 탑다운 방식으로 문제를 해결하였는데, 파이썬이라 메모리복잡도와 시간복잡도를 잡는데에 어려움이 있었다.

N과 M이 클경우에는 재귀방식으로 풀게되면 반복문보다 효율이 떨어진다. 따라서 N과 M이 충분히 크다면, 반복문으로 문제를 해결하려고 노력해야한다.