99클럽 코테 스터디 25일차 TIL - 로봇 조종하기(백준 #2169)

❇️오늘의 학습 키워드 : 로봇 조종하기(백준 #2169)

문제

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())
dp = [list(map(int, input().split())) for _ in range(n)]

# DP 테이블의 첫 번째 행(무조건 왼쪽->오른쪽)
for j in range(1, m):
    dp[0][j] += dp[0][j-1]

# 나머지 행 처리
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])

❇️오늘의 회고

  - 처음에 문제 조건들이 익숙해 bfs로 풀어보려다가 생각을 멈추고 dp를 받아들였다.

  - dp는 왜 풀어도 풀어도 어려운가... 온세상의 dp문제를 다 풀면 좀 익숙해질까...:)

  - 내일 11시, 문제를 풀기 전에 위 문제를 한번 더 복습하고 내일 문제에 사용된 알고리즘에 대해서 공부할 것이다!🙂