[11048] 이동하기

😲 문제

출처
준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력
3 4
1 2 3 4
0 0 0 5
9 8 7 6

출력
31

❗️ 문제 재정의

1. n: 행의 수, m : 열의 수가 주어지고 각각의 칸에 사탕의 개수가 적혀져있다.
2. maze[n][m]으로 도착 시 사탕의 개수가 최대가 되도록 하라.
3. 오른쪽 대각선 아래, 아래, 오른쪽 으로만 이동 가능하다.

배열은 0부터 시작하니 도착지점은 maze[n-1][m-1]이 될 것이다.
오른쪽 대각선 아래 방향은 고려하지 않아도 된다.
사탕은 양수만 존재하기에 오른쪽 대각선 아래 방향으로 간다면 오른쪽을 들린 다음 아래쪽으로 내려가도 되기 때문이다.
즉, 오른쪽 대각선 아래보다 오른쪽->아래로 가는 two step이 무조건적으로 크거나 같다.
DP 를 사용하여 이제까지의 경로를 저장하며 최종으로 얻게될 사탕의 개수를 최대화하는 방향으로 maze[n-1][m-1]에 도착해야한다.

✔ 계획 수립

1. 입력을 받고 maze 생성
2. 열과 행의 수에 맞게 dp 0으로 초기화
3. dp의 첫번째 열과 행을 누적값으로 초기화!

4. 각각의 칸을 방문하며 오른쪽과 아래쪽으로 갔을 경우 어느 것이 최대인지 확인 하며 저장

5. 최종 전체 최대값 출력

왜 출간을 누르게 되면 사진의 크기가 변동이 되는걸까....

👨🏻‍💻 문제 풀이

n,m = map(int, input().split()) # n(행의 수) m(열의 수)
maze = [list(map(int, input().split())) for _ in range(n)] # 각 칸 마다의 사탕의 수

dp = [[0]*m for _ in range(n)] # dp 초기화
dp[0][0] = maze[0][0]

# 첫번째 열 초기화
for i in range(1,n):
    dp[i][0] = dp[i-1][0] + maze[i][0]
# 첫 번째 행 초기화
for j in range(1,m):
    dp[0][j] = dp[0][j-1] + maze[0][j]

# 각각의 칸으로 갔을 때의 최대값을 저장하고 전부 탐색시 전체 최대값이 나오게 된다.
# 주의 할 것은 탐색 범위이다.
# 첫번째 행과 열을 제외한 나머지 칸들을 각각 방문하며 그 칸을 방문할시에 대한 최대값을 저장하여야 한다.
for i in range(1,n):
    for j in range(1, m):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + maze[i][j]

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

😅 회고

어렴풋이 레벤슈타인 거리로 풀면 되겠다는 생각은 들었으나 첫번째 열과 행을 누적 값으로 초기화 시킨다는 것이 생각이 잘 나지 않았다.