BOJ 이동하기

1. BOJ 11048 이동하기

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

코드

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
 
for i in range(N):
    for j in range(M):
        if i==0:
            if j ==0:
                arr[i][j] = arr[i][j]
            else:
                arr[i][j] += arr[i][j-1]
        else:
            if j==0:
                arr[i][j] += arr[i-1][j]
            else:
                arr[i][j] += max(arr[i-1][j], arr[i-1][j-1], arr[i][j-1])
print(arr[-1][-1])

설명

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

위와 같이 입력이 들어온다. 마지막 칸에 도달할 때까지 얻을 수 있는 사탕의 최댓값을 구하면 된다. 

해당 문제에서는 무조건 '대각선 아래, 오른쪽, 아래'로 이동해야 한다. 

반대로 생각해보면 각 위치에서 '대각선 위, 왼쪽, 위' 의 값 중 max 값을 더해서 업데이트하면 된다는 것이다. 

따라서, arr[0] 와 arr[i][0] 의 경우는 예외처리를 해주고, 나머지 그리드는 다음과 같이 업데이트 한다. 

arr[i][j] += max(arr[i-1][j], arr[i-1][j-1], arr[i][j-1])
현재 값             왼쪽       대각선 위       위