2169 - 로봇 조종하기
📌 문제
NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.
지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.
각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.
📋 코드
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
dp = [[[-int(1e9) for _ in range(M+2)] for _ in range(N+1)] for _ in range(3)]
dp[0][1][0], dp[1][1][0], dp[2][1][0] = 0, 0, 0
for i in range(1, M+1):
for k in range(3):
dp[k][1][i] = dp[k][1][i-1] + graph[0][i-1]
for i in range(2, N+1):
for j in range(1, M+1):
dp[0][i][j] = max(dp[0][i][j], dp[0][i-1][j] + graph[i-1][j-1], dp[0][i][j-1] + graph[i-1][j-1])
for j in range(M, -1, -1):
dp[1][i][j] = max(dp[1][i][j], dp[1][i-1][j] + graph[i-1][j-1], dp[1][i][j+1] + graph[i-1][j-1])
for j in range(1, M+1):
dp[2][i][j] = max(dp[0][i][j], dp[1][i][j])
dp[0][i] = dp[2][i]
dp[1][i] = dp[2][i]
print(dp[2][N][M])💡 한마디
3차원 DP 테이블을 만들어 dp[0][i][j]는 왼쪽에서 오른쪽으로, dp[1][i][j]는 오른쪽에서 왼쪽으로 로봇이 움직이며 가치의 합을 구했다. 그 후 dp[2][i][j]에 둘 중 더 큰 값을 넣어가며 답을 도출했다.
