알고리즘: 백준 11048번 이동하기 (feat. python)

백준 11048번 링크입니다.

11048번: 이동하기

 

 

DFS 인줄 알았지만 시간초과가 나길래 다시 보니 다이나믹프로그래밍이였던 문제 

 

dp를 이차원 리스트로 만들어서

 

dp[N][M] = (N, M)까지 오기까지의 합이라고 한다면  

 

dp[N][M] = max(dp[N - 1][M], dp[N][M - 1], dp[N - 1][M - 1]) + maze[N][M]

 

라고 할 수 있다. 

 

 

import sys

input = sys.stdin.readline

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


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


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

print(dp[N][M])

 

 

DFS를 알게 된지 얼마 안됐는데  만약 DFS를 알기전의 나였다면 처음부터 dp로 풀었을 것 같다.

 

물론 DFS로도  풀리긴 하지만 더 빠르고 정확한 방법이 있었다. 초심을 찾고 열심히 하자!