소프티어

다른 분들의 연습문제 톡을 구경하던 도중 DP이지만 저와 다른 방식으로 해결하신 분의 풀이 방법을 보고 배워 가는 내용이 많아서 제가 푼 방법도 공유해 봅니다!

문제를 처음 접했을 때는 2차원 DP 배열을 만들어서 dp[i][j][0]에는 (i, j)번째 칸까지의 최대 수확량을, dp[i][j][1]에는 (i, j)번째 칸까지 수로를 넣은 경로 중 가장 큰 값을 집어넣으려고 했습니다. 하지만 스프링클러를 사용하기 전 수확량이 최대인 경로라고 하더라도, 스프링클러를 사용한 후 수확량이 최대가 아닌 경우가 발생합니다. 예를 들어

4

1 3 5 7

9 1 1 1

1 1 1 1

로 입력값이 주어진 경우, 스프링클러를 사용하지 않았을 때 최대 수확량은 (1+3+5+7+1+1) = 18입니다. 그러나 스프링클러를 사용했을 때 최대 수확량은 (1+18+1+1+1+1) = 23이 됩니다. 따라서 이 방식으로 dp배열을 관리하면 오답을 받습니다.

제가 푼 방식은 2차원 DP 배열을 만들고,

dp[i][j][0]에는 (i, j)번째 칸까지 스프링클러를 사용하지 않은 경우 최대 수확량을,

dp[i][j][1]에는 (i, j)번째 칸까지 스프링클러를 사용한 경우 최대 수확량을 넣어줬습니다.

이때 dp[i][j][1]에는

(i-1, j) 또는 (i, j-1)번째 칸까지 스프링클러를 사용하지 않은 경우 + (현재 칸의 수확량 * 2) 와

(i-1, j) 또는 (i, j-1)번째 칸까지 스프링클러를 사용한 경우 + (현재 칸의 수확량 *1)

중 큰 값이 들어갑니다.

정답을 받은 코드도 함께 첨부합니다!

제 코드에서 이해가 되지 않는 부분이나 개선할 점이 있다면 댓글 남겨주세요!

import sys
input = sys.stdin.readline


N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
dp = [[[0, 0] for _ in range(N)] for _ in range(N)]


for i in range(N):
    for j in range(N):
        up = 0 if not i else dp[i-1][j][0]
        left = 0 if not j else dp[i][j-1][0]
        dp[i][j][0] = max(up, left) + graph[i][j]
        umax = 0 if not i else max(dp[i-1][j][1] + graph[i][j], dp[i-1][j][0] + graph[i][j] * 2)
        lmax = 0 if not j else max(dp[i][j-1][1] + graph[i][j], dp[i][j-1][0] + graph[i][j] * 2)
        dp[i][j][1] = max(umax, lmax, 2*graph[i][j])
print(dp[N-1][N-1][1])