2169번 로봇 조종하기 - Python, DP

 

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

 

코드

 

import sys

# 입력 처리
data = sys.stdin.read().splitlines()
N, M = map(int, data.pop(0).split(" "))

mars = [list(map(int, data.pop(0).split(" "))) for _ in range(N)]
dp = [[[-float('inf')] * 3 for _ in range(M)] for _ in range(N)]

# 첫 번째 행 초기화
dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = mars[0][0]

for y in range(1, M):
    dp[0][y][0] = dp[0][y][1] = dp[0][y][2] = dp[0][y - 1][0] + mars[0][y]

for x in range(1, N):
    # 내려가는 경우 (위쪽에서 오는 값)
    for y in range(M):
        dp[x][y][2] = max(dp[x - 1][y]) + mars[x][y]

    # 오른쪽으로 가는 경우 (왼쪽에서 오는 값)
    dp[x][0][0] = dp[x][0][2]
    for y in range(1, M):
        dp[x][y][0] = max(dp[x][y - 1][0] + mars[x][y], dp[x][y][2])

    # 왼쪽으로 가는 경우 (오른쪽에서 오는 값)
    dp[x][M - 1][1] = dp[x][M - 1][2]
    for y in range(M - 2, -1, -1):
        dp[x][y][1] = max(dp[x][y + 1][1] + mars[x][y], dp[x][y][2])


# 마지막 행의 최대값 출력
print(max(dp[N - 1][M - 1]))

 

 

풀이

 

이 문제의 이동 방식은

 

아래, 왼쪽, 오른쪽으로 이동합니다.

 

목적지 [N - 1][M - 1]의 위치에 도달했을 때

 

가장 높은 값을 가지는 경우를 찾아야합니다.

 

모든 경우를 찾아야하는데,

 

이걸 브루트포스로 하면 시간 초과가 걸리겠죠?

( 1≤N, M≤1,000 )

 

그렇기 때문에

 

[오른쪽으로 가는 경우][왼쪽으로 가는 경우][아래로 내려가는 경우]

 

이렇게 3가지 경우의 수를 기록하는 3차원 리스트를 이용해봅시다.

 

우선 위에서 내려오는 경우 = 위의 칸에서 가장 높은 값 + 현재 칸의 값입니다.

 

오른쪽으로 가는 경우는

 

우선 첫번째 칸을([x][0][0]) 위에서 내려온 값으로 초기화해줍니다.

 

그 후 1부터 M - 1까지 이동하면서

 

( 현재 칸 기준 ) 왼쪽칸의 왼쪽에서 온 값 + 현재칸 값 과 위에서 내려온 값을 비교해서

 

높은 값을 저장해줍니다.

 

왼쪽으로 가는 경우는 이와 정반대로만 진행하면 됩니다.

 

이렇게 모든 경우의 수를 구했다면

 

[N - 1][M - 1] 칸의 값 중 가장 큰 값을 반환해주면 됩니다.

 

 

 

 

 

 

다음에 또 봐요