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

아래, 좌우로만 갈 수 있는 로봇을 조종해서 가장 큰 점수를 얻어서 오른쪽 아래로 도달하는 문제이다.

Python

시도 1 - 실패

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())

mars = list(list(map(int, input().split())) for _ in range(n))

dp = [[-1000] * m for _ in range(n)]

dp[0][0] = mars[0][0]
for i in range(1, n):
    dp[0][i] = mars[0][i] + dp[0][i - 1]

# 점화식
# dp[y][x] = mars[y][x] + max(dp[y-1][x], dp[y][x+1], dp[y][x-1])

dy = [-1, 0, 0]
dx = [0, 1, -1]
visited = [[True] * m for _ in range(n)]

visited[-1][-1] = False


def dfs(sy, sx, visited, dp):
    if dp[sy][sx] != -1000:
        return dp[sy][sx]

    now = mars[sy][sx]

    next = -1000

    for d in range(3):
        ny = sy + dy[d]
        nx = sx + dx[d]

        if 0 <= ny < n and 0 <= nx < m and visited[ny][nx]:
            visited[ny][nx] = False
            tmp = dp[ny][nx]
            next = max(next, dfs(ny, nx, visited, dp))
            visited[ny][nx] = True
            dp[ny][nx] =tmp

    dp[sy][sx] = max(dp[sy][sx], now + next)
    return dp[sy][sx]


print(dfs(n - 1, m - 1, visited, dp))

DFS로 풀어보려했다. 재방문을 방지하고 다른 방향에서 계산한 dp가 영향을 주지 않도록 매번 dp를 초기화 해주었다. 그리고 시간초과로 실패했다.

시도 2

https://wooono.tistory.com/605
이 글의 도움을 받아 해결하였다.

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
dp = list(list(map(int, input().split())) for _ in range(n))

for i in range(1, m):
    dp[0][i] += dp[0][i - 1]

# 위에서 아래로만 갈 수 있기에 그렇게 진행
# 1번 idx 이후 행별로는 좌우 갚 비교하기
for i in range(1, n):
    ltr = dp[i][:]
    rtl = dp[i][:]

    # 왼쪽에서 오른쪽
    for j in range(m):
        if j == 0:
            ltr[j] += dp[i - 1][j]
        else:
            ltr[j] += max(dp[i - 1][j], ltr[j - 1])

    # 오른쪽에서 왼쪽
    for j in reversed(range(m)):
        if j == m - 1:
            rtl[j] += dp[i - 1][j]
        else:
            rtl[j] += max(dp[i - 1][j], rtl[j + 1])

    for j in range(m):
        dp[i][j] = max(ltr[j], rtl[j])

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

위에서 아래로만 진행할 수 있기에 전체 진행방향을 그렇게 제한하고, 각 행별로 왼쪽과 오른쪽 각각 진행만 저장할 배열을 만들고, 진행하면서 위vs왼 그리고 위 vs 오른 이렇게 비교했다. 마지막으로 두 진행방향에 대한 배열을 비교해서 최대값만 남겼다.

문제는 통과했는데 풀리지 않는 의문이 있었다.

dp[i][j]가 최대가 되기 위해서는 dp[i][j-1]을 거쳐야하고, dp[i][j-1]이 최대가 되기 위해서 dp[i][j]를 거쳐야한다면 모순이 아닌가?

GPT한테 물어봤는데 실제로 그런 샘플도 주었다.

mars = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

이 경우 첫번째 행은 오른쪽으로만 갈 수 있기에

[1, 3, 6]

이되고

두번째 행은 왼쪽에서 오른쪽으로 패스(ltr 계산)
ltr[0] = mars[1][0] + dp[0][0] = 4 + 1 = 5
ltr[1] = mars[1][1] + max(dp[0][1], ltr[0]) = 5 + max(3, 5) = 10
ltr[2] = mars[1][2] + max(dp[0][2], ltr[1]) = 6 + max(6, 10) = 16

오른쪽에서 왼쪽으로 패스(rtl 계산)
rtl[2] = mars[1][2] + dp[0][2] = 6 + 6 = 12
rtl[1] = mars[1][1] + max(dp[0][1], rtl[2]) = 5 + max(3, 12) = 17
rtl[0] = mars[1][0] + max(dp[0][0], rtl[1]) = 4 + max(1, 17) = 21

이렇게 계산이 되어 최종적으로

[21, 17, 16]

이 된다. 여기서 dp[1][2]는 오른쪽 방향의 연산을, dp[1][1]은 왼쪽방향의 연산을 선택했고, 선택에서도 각각 dp[1][1]을 거치고, dp[1][2]를 거치는 방향을 선택했다.

이 결과가 모순이 아닌지 의문이 들었다.

GPT는 두 연산이 독립적이기에 모순이 아니라고 했지만 의문이 드는 것이

그럼 dp[i][j]가 최대가 되기 위해서 dp[i][j-1]이 최대일 필요는 없다는 말일까?

라는 의문이 생겼다.
GPT의 답변은 특정 셀의 최대값을 각 방향이 독립적으로 계산하고 그 결과만 저장하기에 서로 영향을 주지 않는다고 하였다. 그러니까 dp[i][j]에는 어찌됐건 최대값만 저장하고 그 다음 셀로 가기위한 점수만 제공해준다고 이해하면 될 것 같은데 더 생각을 해봐야겠다.