[백준] 2169 로봇 조종하기, python

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

 

 

처음에는 백트래킹 dfs로 풀려고 했으나 시간초과가 떴다.

로봇은 아래, 왼쪽, 오른쪽으로만 이동할 수 있으므로 한 row에 대해서 왼쪽에서 오는 경우, 오른쪽에서 오는 경우를 저장해서 둘 중 큰 값을 dp에 저장하는 방식으로 해결하였다.

오른쪽에서 오는 경우는 오른쪽에서 왔을때와 위에서 왔을 때의 최솟값

즉 left[현재 row][현재 col]= max( left [현재 row][오른쪽 col] , left [위쪽 row][현재 col]) + 현재칸에 적힌 수 

왼쪽에서 오는 경우는 왼쪽에서 왔을 때와 위에서 왔을 때의 최솟값이다.

right [현재 row][현재 col]= max( right [현재 row][왼쪽 col] , right [위쪽row][현재col]) + 현재칸에 적힌 수 

 

최종적으로 dp [현재 row][현재 col] = max( left [현재 row][현재 col], right [현재 row][현재 col] )가 된다.

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


n, m = list(map(int, input().split()))
board = [list(map(int, input().split())) for _ in range(n)]

# i,j까지의 최대 가치
dp = [[-float('inf')]*m for _ in range(n)]
dp[0][0] = board[0][0]

for j in range(1,m):
    dp[0][j] = dp[0][j-1] + board[0][j]

for i in range(1,n):
    left = [-float('inf')]*m
    right = [-float('inf')]*m

    # 왼쪽에서 도달하는 경우
    left[0] = dp[i-1][0] + board[i][0]
    for j in range(1,m):
        left[j] = max(left[j-1], dp[i-1][j]) + board[i][j]

    # 오른쪽에서 도달하는 경우
    right[m-1] = dp[i-1][m-1] + board[i][m-1]
    for j in range(m-2,-1,-1):
        right[j] = max(right[j+1], dp[i-1][j]) + board[i][j]
    
    # 왼쪽 오른쪽 중 큰값을 저장
    for j in range(m):
        dp[i][j] = max(left[j], right[j])


print(dp[n-1][m-1])