백준 > 이동하기

❓ 문제

백준 실버2 문제 > 이동하기

❗ 해결

이동은 오른쪽 아래, 위 또는 대각선으로만 이동이 가능하다.
값을 누적해줄 dp 테이블을 하나 생성해준다.

1 2 3 4
0 0 0 5
9 8 7 6

이렇게 있을 때

반복문을 두번 돌린다.

for i in range(n):
	for j in range(m):

i(행)가 0이거나 n, 즉 행의 맨 끝이나 맨 처음일 때는 j-1에 있는 값에 누적해주고
j(열)이 0이거나 m 일대는 i-1에 있는값만 누적하고,
그 외의 경우

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 현재 값

을 누적해주면 된다.

n,m = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * m for _ in range(n)]

dp[0][0] = maze[0][0]

for i in range(n):
    for j in range(m):

        if i == 0 or i == n:
            dp[i][j] = dp[i][j-1] + maze[i][j]
        elif j == 0 or j == m:
            dp[i][j] = dp[i-1][j] + maze[i][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + maze[i][j]

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

조금 더 쉽게 풀수 있는 방법이 있었다..

다른분의 코드
https://dailylifeofdeveloper.tistory.com/122

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
dp = [[0] * (M + 1)] * (N + 1)
candy = []

for i in range(N):
    candy.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]) + candy[i-1][j-1]

print(dp[N][M])

기저상태 설정하는게 좀 달라서 그랬던것 같은데.. dp는 아직 많이 풀어봐야할것 같다.
뭔가 점화식은 도출하는데 성공했지만, 아직 많이 부족하다..

풀긴 했는데 뭔가 찜찜한 이 느낌