백준_2169_로봇 조종하기

문제

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

2169번: 로봇 조종하기

풀이

DP

위치를 위, 오른쪽, 왼쪽으로 움직이면서 가장 큰 경우를 board에 저장한다.

1. 0번째 행의 경우, 오른쪽으로만 이동이 가능하다.

2. 1번째 ~ N-1번째 행까지, 오른쪽/왼쪽으로 이동이 모두 가능하다.

2-1. 왼쪽과 위쪽을 비교하여 구한 배열과

2-2. 오른쪽과 위쪽을 비교하여 구한 배열을 비교해 

해당 위치에서 가질 수 있는 최대값을 board에 저장한다.

 

코드

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
board = [list(map(int, input().strip().split())) for i in range(N)]

# 맨 윗줄
for j in range(1, M) :
    board[0][j] += board[0][j-1]
        
# 나머지
for i in range(1, N) :   
    startLeft = [board[i][j]+board[i-1][j] for j in range(M)]
    startRight = [board[i][j]+board[i-1][j] for j in range(M)]
    
    # →
    for j in range(1, M) : 
        startLeft[j] = max(startLeft[j], startLeft[j-1]+board[i][j]) 
    
    # ←
    for j in range(M-2, -1, -1) : 
        startRight[j] = max(startRight[j], startRight[j+1]++board[i][j])
    
    # 선택
    for j in range(M) : 
        board[i][j] = max(startLeft[j], startRight[j])

print(board[-1][-1])