[백준/python] 11048- 이동하기

n ,m = tuple(map(int, input().split()))
miro = [
    list(map(int, input().split()))
    for _ in range(n)
]
dp = [
    [0] * m
    for _ in range(n)
]

for i in range(n):
    for j in range(m):
        if i == 0 and j == 0:
            dp[0][0] = miro[0][0]
        elif i == 0:
            dp[0][j] = dp[0][j - 1] + miro[0][j]
        elif j == 0:
            dp[i][0] = dp[i - 1][0] + miro[i][0]
        else:
            dp[i][j] = max(dp[i - 1][j] + miro[i][j], dp[i][j - 1] + miro[i][j], dp[i - 1][j - 1] + miro[i][j])

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

| 알고리즘

1. 미로 맵을 받고, dp맵도 미로와 갯수가 같게 0우로 채워준다.

2. 시작점 즉, i == 0과 j == 0 일 때는 미로 첫 점을 dp 첫 점으로 추가

3. i가 0이면 즉, 가로 맨 위면 왼쪽 dp와 자신의 점 값을 더한게 해당 dp 값이고 j가 0, 즉 세로 맨 왼쪽이면 자신의 바로 위 dp값과 자신의 점 값을 더한게 해당 dp 값

4. i, j가 1, 1부터는 (i ,j)에 해당하는 미로값 + 왼쪽, 왼쪽 대각선, 위쪽의 dp값을 받아서 max 함수로 최댓값을 해당 dp값으로 갱신해준다.

 

dp의 개념을 완벽하게 이해한 문제. 신기하게도 dp 문제는 많이 틀리지 않고 그냥 맞춘다. 전에 스터디원들의 설명이 어렴풋하게 기억났으나 다시 풀어보니깐 확실히 알겠다. 이번게 모각코 마지막 문제인데.. 방학동안 고생했다!!!