백준 11048 이동하기 파이썬

백준 11048 이동하기 풀이

접근방식

1. 이동할 때마다 사탕의 최댓값을 저장할 dp 리스트를 만듭니다.
2. 이동할 때마다 현재 위치한 사탕의 갯수 + (왼쪽 대각선 사탕, 바로 왼쪽 사탕, 바로 위 사탕) 중 가장 큰 값을 저장합니다.
3. 결과적으로 [n][m] 위치에는 최댓값이 저장됩니다.

dp리스트의 크기를 (n+1 * m+1)를 지정하면 첫번째 행과 첫번째 열에 대해서
문제없이 0을 더해줄 수 있어서 편리합니다.

정답코드

import sys
input = lambda: sys.stdin.readline().rstrip()

n,m = map(int, input().split())

dp = [[0] * (m+1) for _ in range(n+1)]
arr = []

for _ in range(n):
    arr.append(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]) + arr[i-1][j-1]

print(dp[n][m])

해당 문제는 실버 1레벨의 다이나믹 프로그래밍 문제였습니다.

이동하면서 최댓값을 갱신해주면 되는 문제였기 때문에

어렵지 않게 풀 수 있었습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady