백준 2169: 로봇 조종하기 (Python)

접근

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

2169번: 로봇 조종하기

처음엔 dfs를 이용한 dp를 생각해보았지만 해결하지 못했다.
로봇이 왼쪽, 오른쪽, 아래 방향으로만 이동할 수 있다는 점에 착안하여 i 행에서 왼쪽으로 움직일 때와 오른쪽으로 움직일 때를 각각 계산하여 최대값을 구하는 식으로 dp를 이용하여 해결할 수 있었다.

코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
dp = []
for i in range(N):
    dp.append(list(map(int, input().split())))
for i in range(1, M):
    dp[0][i] += dp[0][i - 1]
for i in range(1, N):
    dplr = dp[i][:]
    dprl = dp[i][:]
    for j in range(M):
        if j == 0:
            dplr[j] += dp[i - 1][j]
            dprl[M - 1 - j] += dp[i - 1][M - 1 - j]
        else:
            dplr[j] += max(dp[i - 1][j], dplr[j - 1])
            dprl[M - 1 - j] += max(dp[i - 1][M - 1 - j], dprl[M - j])
    for j in range(M):
        dp[i][j] = max(dplr[j], dprl[j])
print(dp[-1][-1])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!