[백준] 용액 풀이

이동 방향은 오른쪽, 아래, 오른쪽 아래로 총 3가지인데 상식적으로 한번에 오른쪽 아래로 가는 것 보다 오른쪽을 지난 후 아래 혹은 아래로 간 뒤 오른쪽으로 가는 것 처럼 중간 지점을 거쳐서 가는 것이 낫다는 것을 알 수 있습니다.

즉, 현재 인덱스의 최댓값은 max(왼쪽 인덱스의 값 + 현재 인덱스의 값, 위쪽 인덱스의 값 + 현재 인덱스의 값)으로 이루어집니다.

기존 arr 배열과 dp 배열을 둔 뒤, dp[0][0] 에 arr[0][0]을 대입하였고, 반복문을 돌며 위의 방식대로 값을 업데이트 해 줍니다.

여기서 주의할 점은
1)현재 인덱스가 0,0인 경우 continue
2)현재 인덱스가 맨 왼쪽 혹은 맨 위쪽에 위치하는 경우 각각 위쪽, 왼쪽과의 연산을 통해 dp 배열을 업데이트 하면 됩니다.

from sys import stdin

N, M = map(int, stdin.readline().split())
arr = []
dp = [[0 for i in range(M)] for j in range(N)]

for i in range(N):
    arr.append(list(map(int, input().split())))

dp[0][0] = arr[0][0]

for i in range(N):
    for j in range(M):

        if i == 0 and j == 0:
            continue

        elif i == 0:
            dp[i][j] = dp[i][j - 1] + arr[i][j]

        elif j == 0:
            dp[i][j] = dp[i - 1][j] + arr[i][j]

        else:
            dp[i][j] = max(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j])

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