로봇 조종하기 (2169번) - 백준 (BOJ)

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

2169번: 로봇 조종하기

 

백준 - 로봇 조종하기 (2169번)

 

난이도 : Gold 2

알고리즘 : Dynamic Programming (DP)

풀이 소요 시간 : 50 mins

Time Complexity : O( N * M )

 

import sys
input = sys.stdin.readline


if __name__ == '__main__':
    N, M = map(int, input().split())

    prev = list(map(int, input().split()))
    for i in range(1, M):
        prev[i] += prev[i-1]

    for _ in range(N-1):
        cur = list(map(int, input().split()))
        l = [0] * M
        r = [0] * M
        l[0] = prev[0] + cur[0]
        r[~0] = prev[~0] + cur[~0]
        for i in range(1, M):
            l[i] = max(prev[i], l[i-1]) + cur[i]
            r[~i] = max(prev[~i], r[~(i-1)]) + cur[~i]
        prev = [max(ll, rr) for ll, rr in zip(l, r)]
    print(prev[-1])

 

DP로 풀 수 있는 문제였다.

 

---

 

먼저 첫 행은 왼쪽에서 오른쪽으로 누적해서 더한다. (누적 합)

[ 10 25 7 8 13 ]  →  [ 10 35 42 50 63 ]

 

---

 

둘째 행 부터는

 

prev : 바로 이전 행(row)에서 구한 최대 가치의 값들 list
cur : 현재 입력받은 행(row)의 값들 list
l : 현재 행의 왼쪽에서 오른쪽 방향 최대 가치 저장해두는 list
r : 현재 행의 오른쪽에서 왼쪽 방향 최대 가치 저장해두는 list

 

1. 왼쪽부터 오른쪽 방향으로,

왼쪽에서 오른쪽으로 가는 경우와, 위에서 아래로 가는 경우 중 큰 값을 현재 cell 값에 더한다.

l[i] = max(prev[i], l[i-1]) + cur[i]

 

2. 오른쪽부터 왼쪽 방향으로,

오른쪽에서 왼쪽으로 가는 경우와, 위에서 아래로 가는 경우 중 큰 값을 현재 cell 값에 더한다.

r[~i] = max(prev[~i], r[~(i-1)]) + cur[~i]

 

3. 1, 2에서 만든 리스트들의 각 원소를 비교해서,

더 큰 값들로만 구성된 리스트를 만든다.

prev = [max(ll, rr) for ll, rr in zip(l, r)]

 

현재 행의 각 열의 값들이 바로,

(1, 1)에서 현재 (행, 열)까지 엳을 수 있는 최대의 가치이다.

 

---

 

마지막 행까지 위 과정을 모두 진행하면,

마지막 행의 마지막 열 (N, M)의 값이 바로

얻을 수 있는 최대의 가치이다.

print(prev[-1])