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

💻 문제 - G2

👉 제출 코드

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

# 첫 번째 행 업데이트: 무조건 오른쪽
for j in range(1, m):
    dp[0][j] += dp[0][j-1]
    
# 나머지 행 업데이트
for i in range(1, n):
    
    # 두 경우를 담을 임시 배열 생성
    left_to_right = dp[i][:] # 왼쪽에서 오른쪽
    right_to_left = dp[i][:] # 오른쪽에서 왼쪽
    
    # case1: 왼쪽에서 오른쪽
    for j in range(m):
        if j == 0: # 첫번째 열일 경우, 위에서 내려오는 경우
            left_to_right[j] += dp[i-1][j]
        else: # 나머지 열인 경우, 위에서 내려오는 경우와 왼쪽에서 오는 경우
            left_to_right[j] += max(dp[i-1][j], left_to_right[j-1])
            
    # case2: 오른쪽에서 왼쪽
    for j in range(m-1, -1, -1):
        if j == m-1: # 마지막 열일 경우, 위에서 오는 경우
            right_to_left[j] += dp[i-1][j]
        else: # 나머지 열인 경우, 위에서 내려오는 경우와 오른쪽에서 오는 경우
            right_to_left[j] += max(dp[i-1][j], right_to_left[j+1])
    
    # 두 가지 임시 배열을 비교하여 최대값으로 업데이트
    for j in range(m):
        dp[i][j] = max(left_to_right[j], right_to_left[j])

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