문제
NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.
지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.
각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.
입력
첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.
출력
첫째 줄에 최대 가치의 합을 출력한다.
예제 입력 1
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예제 출력 1
319나의 풀이
import sys
input = sys.stdin.readline
N, M = map(int, input().split()) #N * M 크기의 행렬
dp = []
for _ in range(N):
dp.append(list(map(int, input().split())))
for j in range(1, M):
dp[0][j] += dp[0][j-1] #첫번째 행 최댓값 업데이트
for i in range(1, N):
#2가지 임시 배열 생성
left_to_right = dp[i][:] #왼 -> 오
right_to_left = dp[i][:] #오 -> 왼
#왼쪽에서 오른쪽으로 가는 경우
for j in range(M):
#첫번째 열은 위에서 오는 경우밖에 없음
if j == 0:
left_to_right[j] += dp[i-1][j]
#나머지 열은 위에서 내려오는 경우와 왼쪽에서 오는 경우를 비교
else:
left_to_right[j] += max(dp[i-1][j], left_to_right[j-1])
#오른쪽에서 왼쪽으로 가는 경우
for j in range(M-1, -1, -1):
#마지막 열은 위에서 내려오는 경우 밖에 없음
if j == M - 1:
right_to_left[j] += dp[i-1][j]
#나머지 열은 위에서 내려오는 경우와 오른쪽에서 오는 경우를 비교
else:
right_to_left[j] += max(dp[i-1][j], right_to_left[j+1])
#두 임시 배열을 비교해서 더 큰 값으로 dp를 업데이트
for j in range(M):
dp[i][j] = max(left_to_right[j], right_to_left[j])
print(dp[N-1][M-1])풀이 과정
우선 풀이는 여기를 참고 했다.
로봇이 아래와 오른쪽으로만 갈 수 있었다면 참 쉬운 문제였겠지만 오른쪽으로도 가는 바람에 정말 번거로운 문제가 되어 버렸다.
처음에는 해당 칸을 방문했는지를 기록하는 dp list와 해당 칸을 방문 했을 때의 최대값을 기록하는 dp list가 둘 다 필요하다고 생각하고 지레 겁을 먹었지만, 한번 방문한 칸을 다시 갈 수 없다는 규칙 때문에 로봇이 갈 수 있는 경로가 생각보다 더 한정적이었다.
우선 첫 행에서 로봇이 할 수 있는 행동은 오른쪽으로 가던가, 아래로 가던가 둘 중 하나이다.
두번째 행 부터는 최대값을 3번 비교하면 되는데, 우선 위에서 왔을 때와 왼쪽에서 왔을 때 더 큰 값을 임시 배열left_to_right에 기록하고, 다음으로 위에서 왔을 때와 오른쪽에서 왔을 때 더 큰 값을 임시 배열right_to_left에 기록한다. 그 다음 두 임시 배열에서 각각 더 큰 값으로 dp를 업데이트 해주면 되는 것이다.
