[백준 2169번] 로봇 조종하기 (Python3)

import sys
input = sys.stdin.readline
INF = 10**9

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

mars = []
for i in range(N):
  mars.append([*map(int,input().split())])

DP = [[[-INF]*(M+2) for i in range(N+1)] for i in range(2)]
DP[0][0][1]  = 0

for y in range(1,N+1):
  for x in range(1,M+1):
    DP[0][y][x] = max(max(DP[0][y-1][x],DP[1][y-1][x]),DP[0][y][x-1])+mars[y-1][x-1]
    x = M+1-x
    DP[1][y][x] = max(max(DP[0][y-1][x],DP[1][y-1][x]),DP[1][y][x+1])+mars[y-1][x-1]

print(max(DP[0][N][M],DP[1][N][M]))

구현은 간단한데 아이디어가 생각보다 까다로웠다.

 

DP리스트를 두개로 만드는 것이 핵심이다. 오른쪽으로 탐사하는 DP, 왼쪽으로 탐사하는 DP 두개로 나누어서, DP0에는 오른쪽으로 탐사할 때의 최솟값을, DP1에는 왼쪽으로 탐사할 때의 최솟값을 담으면 된다.

 

아이디어만 떠올리면 구현하는거 자체는 간단하게 해결할 수 있을 것이다.

 

 

오늘의 교훈) DP를 조건에 따라 분리하자