문제

문제 이해

문제가 정말 재밌다. DP알고리즘을 배우다가 그 예시로 다뤘던 문제인데, 좌표상에서 움직여야 해서 처음에는 DFS/BFS로 풀어야 한다고 생각했다. 하지만 특정한 값에만 가는 것도 아니고, 최단거리를 뭍는 것도 아니다. (현재 DFS/BFS에 대한 이해도가 좀 떨어지긴 했지만.. 복습해야겠다. 다익스트라 같이 가중치로 가면 안되려나 모르겠다.) 뭐 아무튼 DP로 문제 풀이가 가능하다.

그러니까 한 좌표에 가려고 하면 방법이 3가지가 존재한다.

arr[i][j]라고 할때,

1. arr[i-1][j]
2. arr[i][j-1]
3. arr[i-1][j-1]

이 세가지 중에서 가장 큰 값을 이용하면 된다. 어떤 점이든 저렇게 세 종류 중에서 가장 큰 값을 우선적으로 고른다. 하지만 그렇게 되면 1행/1열의 값은 어떻게 처리해야 하는지 고민될거다. 세로는 위에 있는 것에서 가중치가 쌓이고, 가로는 왼쪽에 있는 것에서부터 가중치가 쌓이게, 메인 로직을 실행하기 전에 두 줄은 따로 처리를 해준다. 그러면 초기값을 부여해준 1행/1열에서 값을 비교하면서 나머지 칸에 가중치(사탕합)값이 들어가게 된다.

코드

# 백준 11048번 이동하기

# 0. 입력받기기
N, M = map(int, input().split())

matrix = []
for i in range(N):
    matrix.append(list(map(int, input().split())))

# 1. dp리스트 만들기기
dp = [[0] * M for _ in range(N)]

# 2. dp의 1행과 1열에 값을 넣는다다
dp[0][0] = matrix[0][0] # 첫dp값은 입력된 첫값과 같음

for i in range(1, M): # 1행 값넣기 
    dp[0][i] = dp[0][i-1] + matrix[0][i]

for j in range(1, N): # 1열 값넣기기
    dp[j][0] = dp[j-1][0] + matrix[j][0]

# 3. 나머지 값 구해서 dp에 채워넣기기
# 1행/1열을 제외한 나머지 값 넣기
# 한점으로 갈 수 있는 경우가 세개, 그중에 가장 큰 값을 dp리스트에 해당 좌표에 넣는다

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

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

주의할 것은 인덱스 오류다. DFS/BFS문제를 풀때도 비슷하지만 인덱스 오류가 나기가 쉽다.