백준 11048: 이동하기 (Python)

접근

https://www.acmicpc.net/problem/11048

11048번: 이동하기

얼핏 dfs나 bfs 문제로 보였지만, 다이나믹 프로그래밍을 이용하여 쉽게 풀 수 있었다.

(r, c) 칸에서 이동할 수 있는 방향은 세방향으로, (r + 1, c), (r, c + 1), (r + 1, c + 1) 이다. 이 점을 반대로 말하면 (r, c) 칸으로 올 수 있는 바로 전 칸은 (r - 1, c), (r, c - 1), (r - 1, c - 1) 이 세 칸이다. 즉 (r, c) 위치에서 최대값을 얻기 위해서는 dp 배열의 (r - 1, c), (r, c - 1), (r - 1, c - 1) 칸 중 가장 큰 값과 (r, c) 칸의 값을 더해야 한다.

코드

N, M = map(int, input().split())
maze = [[0 for _ in range(M + 1)]]
for i in range(N):
    maze.append([0] + list(map(int, input().split())))
dp = [[0] * (M + 1) for _ in range(N + 1)]

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

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

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!