문제
문제 : https://www.acmicpc.net/problem/11048
1 * 1 크기의 방에 사탕이 놓여져 있는 N * M 크기의 미로가 있다고 하자. 미로의 가장 왼쪽 윗 방의 좌표는 (1,1)이고, 가장 오른쪽 아랫방 좌표는 (N, M)이다. 또한 사람이 (r, c) 좌표의 방에 위치하고 있으면 (r+1, c), (r, c+1), (r+1, c+1) 방향으로만 이동할 수 있고, 방을 방문할 때마다 방에 놓여진 사탕을 모두 가져갈 수 있다.
사람이 (1,1) 좌표 방에서 (N, M) 좌표 방으로 미로를 빠져나온다고 할 때, 가져올 수 있는 사탕 개수의 최대값을 구하여라.
접근
이 문제도 동적 계획법과 관련된 문제다. 현재 위치한 방을 어떻게 왔는지 고려해보면 아래 그림을 떠올릴 수 있다.
먼저 맨 위에 위치한 방은 왼쪽 방을 지나야 한다.
그리고 맨 왼쪽에 위치한 방은 위쪽 방을 지나야 한다.
그리고 그 외의 방은 왼쪽 방, 위쪽 방, 왼쪽 위에 위치한 방을 지나야 한다. 단, 가져오는 사탕의 수가 최대가 되기 위해서는 세 개의 방 중 지금까지 가져온 사탕 수가 최대인 방을 지나야 한다.
따라서 테이블에는 방의 좌표와 해당 방까지 이동하면서 가져온 사탕의 최대값을 저장할 수 있도록 한다.
풀이
1. 미로의 크기 입력
N, M = map(int, sys.stdin.readline().split())
2. 미로 내 사탕 수 입력
miro = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
3. 테이블 초기화
미로의 크기와 동일한 크기로 초기화한다. 값은 0으로 초기화했다.
dp = [[0 for j in range(M)] for i in range(N)]
4. 죄표 별 최대 사탕 수 업데이트
for i in range(N):
for j in range(M):
# (1, 1) 방
if i == 0 and j == 0:
val = 0
# (1, *) 방
elif i == 0:
val = dp[i][j - 1]
# (*, 1) 방
elif j == 0:
val = dp[i - 1][j]
else:
val = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
dp[i][j] = val + miro[i][j]
5. 가장 오른쪽 밑 방의 값을 출력한다.
print(dp[i][j])
전체 코드는 다음과 같다.
import sys
N, M = map(int, sys.stdin.readline().split())
miro = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
dp = [[0 for j in range(M)] for i in range(N)]
for i in range(N):
for j in range(M):
if i == 0 and j == 0:
val = miro[i][j]
elif i == 0:
val = dp[i][j - 1] + miro[i][j]
elif j == 0:
val = dp[i - 1][j] + miro[i][j]
else:
val = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + miro[i][j]
dp[i][j] = val
print(dp[i][j])