[동적계획법/DP] 백준 11048 이동하기 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11048번: 이동하기

 

 

 

2. 문제 풀이

 (0, 0)부터 (N-1, M-1)까지 우하향으로 이동하며 최대 점수를 획득하는 문제입니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 DP 문제입니다. 한 줄씩 최대 누적합을 (N-1, M-1)까지 계산합니다.

 

1	1	1	2
2	2	1	2

 위와 같은 미로를 예시로 들어보겠습니다.

 

 

1	2	3	5

 왼쪽부터 오른쪽까지, 누적합을 계산합니다. 1줄 4번째 칸의 최대 사탕 수는 5입니다. 윗 줄이 없기 때문에, 왼쪽에서 오른쪽으로 오는 경우 밖에 없습니다.

 

 

1 (↘)	2 (↓)	3	5
3 (→)	5

 그 다음 줄부터 고민을 해야 합니다. 2줄 2번째 칸으로 올 수 있는 경우의 수는 총 3가지입니다.

• 1줄 첫째칸에서 대각선으로 이동 => 1+2 = 3
• 1줄 둘째칸에서 아래로 이동 => 2+2 = 4
• 2줄 첫째칸에서 오른쪽으로 이동 => 3+2 = 5

 그 중 가장 큰 값이 되는 경우를 선택합니다. 여기선, 오른쪽으로 이동입니다.

 

cache[i][j] = max(cache[i-1][j], cache[i][j-1]) + maze[i][j]

 사실, 대각선 이동은 최대가 될 일이 없습니다. 사탕의 개수는 무조건 0 이상이므로, 한 칸이라도 더 밟는 게 이득입니다. 따라서, 위에서 아래로 이동하는 경우와 왼쪽에서 오른쪽으로 이동하는 경우만 비교합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
maze = [[0]*M]
for _ in range(N):
    maze.append(list(map(int, input().split())))

# DP
cache = [[0]*M for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(M):
        cache[i][j] = max(cache[i-1][j], cache[i][j-1]) + maze[i][j]
print(cache[N][M-1])

 위 점화식에서 문제점은 '첫 번째 줄'입니다. 첫 번째 줄은 위에서 아래로 내려오는 경우가 없습니다. 따라서, 모두 0인 0번째 줄을 임의로 만들어줍니다. 그러면 점화식대로 DP를 진행할 수 있습니다.