[백준] 11048번. 이동하기

[백준] 11048번. 이동하기 바로가기

아이디어

처음 아이디어

• (0, 0)에서 출발해서 bfs로 갈 수 있는 방향 사탕 더해준다.
• 방문처리 하지 않는다. 어떤 경로로 와야 최댓값인지 모르니까
• (N, M)에 도착할 때 안멈추고 사탕의 수를 리스트에 다 넣어서 최댓값을 찾는다.

문제상황

메모리 초과

해결방안

• dp[r][c]의 최댓값은 3개 중 하나(거꾸로 생각한다)

1. dp[r-1][c] + candy
2. dp[r][c-1] + candy
3. dp[r-1][c-1] + candy

그래 이게 DP지 🤯
DP 문제 많이 풀어봐야겠다.

시간 복잡도

• O(N * M)

코드

import sys
input = sys.stdin.readline

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

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

print(dp[N][M])