[DP] 백준 2169번 “로봇 조종하기” Python 풀이

문제 링크

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

풀이

• 특정 좌표로 갈 수 있는 방법은 아래와 같습니다.

  • 위에서 오는 것
  • 왼쪽에서 오는 것
  • 오른쪽에서 오는 것

• 5x5 샘플 데이터를 통해 좌표 값들을 업데이트해보겠습니다.

  

• 먼저, 첫 번째 행은, 왼쪽에서 오른쪽로 진행하는 경우 밖에 없으므로, 각 좌표까지의 최대 가치를 먼저 업데이트할 수 있습니다.

  

• 이제 나머지 행들을 순서대로 탐색하며 좌표값들을 업데이트해야합니다.

• 이때, 각 행들을 두 가지 임시 배열(왼쪽 → 오른쪽으로 진행 시 구해진 최댓값, 오른쪽 → 왼쪽으로 진행 시 구해진 최댓값)로 표현한 뒤, 두 임시 배열을 비교함으로써, DP 테이블의 각 좌표를 최대값으로 업데이트할 수 있습니다.

  • 왼쪽 → 오른쪽으로 진행될 경우, 임시 배열의 각 좌표값들은, 위에서 왔을 때의 값과 왼쪽에서 왔을 때의 값이 비교되어, 최대값으로 업데이트됩니다.

    

  • 오른쪽 → 왼쪽으로 진행될 경우, 임시 배열의 각 좌표값들은, 위에서 왔을 때의 값과 오른쪽에서 왔을 때의 값이 비교되어, 최대값으로 업데이트됩니다.

    

  • 이후, 두 임시 배열을 비교함으로써, DP 테이블의 각 좌표를 최대값으로 업데이트할 수 있습니다.

    

코드

import sys

# 행렬 크기 입력
n, m = map(int, sys.stdin.readline().split())

# DP 테이블
dp = []

# DP 테이블에 각 행 추가
for _ in range(n):
    dp.append(list(map(int, sys.stdin.readline().split())))

# DP 테이블의 첫 번째 행 업데이트
for j in range(1, m):
    dp[0][j] += dp[0][j-1]

# DP 테이블의 나머지 행 업데이트
for i in range(1, n):
    # 두가지 임시 배열 생성
    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])

    # 두 가지 임시 배열을 비교해, 각 좌표값들을 최대값으로 업데이트
    for j in range(m):
        dp[i][j] = max(left_to_right[j], right_to_left[j])

print(dp[n-1][m-1])

참고

• https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=220808155184
• https://youngyin.tistory.com/192