[백준]11048 이동하기.py

문제 이해하기

• 오른쪽(r+1, c), 아래쪽(r, c+1), 오른쪽 아래 대각선(r+1, c+1)으로만 이동할 수 있으며 이동하면서 사탕을 최대한 많이 모으기

소스코드

N, M = map(int, input().split())
room = []
candy = [[0]*(M+1)] * (N+1)
for i in range(N):
    room.append(list(map(int, input().split())))

for i in range(1, N+1):
    for j in range(1, M+1):
            candy[i][j] = max(candy[i-1][j], candy[i][j-1], candy[i-1][j-1]) + room[i-1][j-1]

print(candy[N][M])

candy[i][j] = max(candy[i-1][j], candy[i][j-1], candy[i-1][j-1]) + room[i-1][j-1]

은 아래 그림과 같다.
candy[1][1]를 둘러싼 값 중에서 큰 값을 room[0][0]과 더한다.
마찬가지로 candy[2][2]를 둘러싼 값 중에서 큰 값을 room[1][1]과 더한다.

표를 다 채우면 마지막 숫자가 31이 나온다.

DP는 아직 낯설어서 문제 푸는데 오래걸린다😥