알고리즘💻/DP
BOJ 11048: 이동하기
호프
2021. 8. 1. 23:27
https://www.acmicpc.net/problem/11048
11048번: 이동하기
준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는
www.acmicpc.net
이것도 dp를 활용하여 푸는 기본적인 유형이었다. 간단하게 점화식을 짤 수 있었다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = []
for _ in range(N):
arr.append(list(map(int, input().split())))
dp = [[0]*M for _ in range(N)]
dp[0][0] = arr[0][0]
for i in range(1, N):
dp[i][0] = dp[i-1][0] + arr[i][0]
for i in range(1, M):
dp[0][i] = dp[0][i-1] + arr[0][i]
for i in range(1, N):
for j in range(1, M):
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + arr[i][j]
print(dp[N-1][M-1])