99클럽 코테 스터디 TIL

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

 

• 로봇은 아래,오른쪽,왼쪽으로만 움직이며 한번 지나친 곳은 지나가지 못함
• 해당 row에서 한번 왼쪽으로 움직으면 왼쪽으로만, 오른쪽으로 움직이면 오른쪽으로만 움직임
• 왼쪽으로 움직였을 경우와 오른쪽으로 움직였을 경우 두가지로 나누어 계산하면 모든 경우의 수 계산이 가능해짐
  • r,c 지점에서의 최대 값은 윗층(r-1,c)에서 내려온 값, 왼쪽(r,c-1)에서 온 값, 오른쪽(r,c+1)에서 온 값 세가지로 분류 가능
  • 왼쪽, 오른쪽으로만 움직일 경우로 분리하고 각각의 경우에 최대값을 찾은 후 병합

 

import sys
input = sys.stdin.readline
def solution(R,C,arr):
    for c in range(1,C):
        arr[0][c] += arr[0][c-1]
    for r in range(1,R):
        leftMovingArr = arr[r][:]
        rightMovingArr = arr[r][:]
        leftMovingArr[0] += arr[r-1][0]
        for c in range(1,C):
            leftMovingArr[c] += max(arr[r-1][c],leftMovingArr[c-1])
        rightMovingArr[-1] += arr[r-1][-1]
        for c in range(C-2,-1,-1):
            rightMovingArr[c] += max(arr[r-1][c],rightMovingArr[c+1])
        for c in range(C):
            arr[r][c] = max(leftMovingArr[c],rightMovingArr[c])
    return arr[R-1][C-1]

R,C = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(R)]
ans = solution(R,C,arr)
print(ans)