[백준/2169] 로봇 조종하기 (Python)

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

2169번: 로봇 조종하기

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:28:30

 

---

 

문제 설명

 

NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.

지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.

각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

 

첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.

 

출력

 

첫째 줄에 최대 가치의 합을 출력한다.

 

입력 예시

 

5 5
10 25 7 8 13
68 24 -78 63 32
12 -69 100 -29 -25
-16 -22 -57 -33 99
7 -76 -11 77 15

 

출력 예시

 

319

 

 

---

 

풀이

 

DP 문제. 왼쪽 / 오른쪽 / 아래로 이동할 수 있어 언뜻 보면 어려워 보이지만, 한번 지나간 좌표는 다시 돌아갈 수 없다는 제약조건을 이해해보자. 즉 한 층에서는 왼쪽 / 오른쪽 일방통행만 가능하다.

 

따라서 왼쪽 방향으로 진행하는 Left Dp와, 오른쪽 방향으로 진행하는 Right Dp를 따로 구해볼 수 있다. 이 때,

 

• Left DP : L[0] = dp[i-1][0] + value[i][0], L[j] = max(L[j-1], dp[i-1][j]) + value[i][j]
• Right DP : R[M-1] = dp[i-1][M-1] + value[i][M-1], R[j] = max(R[j+1], dp[i-1][j]) + value[i][j]

가 성립한다! 최종적인 i행 j열의 DP값 dp[i][j] = max(L[j], R[j]) 이 성립하므로, O(NM)의 시간복잡도 내에 해결 가능하다.

 

풀이 코드

import sys
input = sys.stdin.readline
MAX = float('inf')
N, M = map(int, input().split())
value_list = [list(map(int, input().split())) for _ in range(N)]
dp = [[-MAX]*M for _ in range(N)]
for i in range(M) :
  if i == 0 :
    dp[0][i] = value_list[0][i]
  else :
    dp[0][i] = dp[0][i-1] + value_list[0][i]

for i in range(1, N) :
  Ldp, Rdp = [-MAX]*M, [-MAX]*M
  Ldp[0] = dp[i-1][0] + value_list[i][0]
  Rdp[-1] = dp[i-1][-1] + value_list[i][-1]
  for j in range(1, M) :
    Ldp[j] = max(Ldp[j-1], dp[i-1][j]) + value_list[i][j]
    Rdp[-1-j] = max(Rdp[-j], dp[i-1][-1-j]) + value_list[i][-1-j]
  for j in range(M) :
    dp[i][j] = max(Ldp[j], Rdp[j])
        
print(dp[-1][-1])

풀이 완료