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

1일 1PS 8일차!

문제

---

골드 2

• 아래로 이동할 수 있지만 위로는 이동할 수 없다.
• 즉, 아래로 이동하면서 한 층씩 최대 값을 업데이트해나가면 된다.

포인트

---

1. 첫 번째 행부터 왼쪽으로 진행하면서 최대 값을 업데이트한다.
2. 두 번째부터는 위에서 내려온 값들과 왼쪽, 오른쪽으로 이동할 때의 값을 비교해 최대값을 저장한다.

코드

---

import sys
input = sys.stdin.readline

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

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

for i in range(1, n) :
    left = [map[i][j] + map[i-1][j] for j in range(m)]
    right = [map[i][j] + map[i-1][j] for j in range(m)]

    for j in range(1, m) :
        left[j] = max(left[j], left[j-1] + map[i][j])

    for j in range(m-2, -1, -1) :
        right[j] = max(right[j], right[j+1] + map[i][j])

    for j in range(m) :
        map[i][j] = max(left[j], right[j])

print(map[-1][-1])