[알고리즘][Python] 백준(BOJ) 11048 이동하기_파이썬

 

11048 이동하기    https://www.acmicpc.net/problem/11048

11048번: 이동하기

 

 

 

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이 1

<내용>

• 미로에 있는 사탕을 배열로 저장한다.
• (r, c)에서 (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있으므로 (n, m)은 (n-1, m), (n, m-1), (n-1, m-1)에서 오는 것이 가능한다.
• 그 중 가장 사탕을 많이 가져오는 것이 최댓값을 구하는 방법이다.
• 이때, 미로의 가장 오른쪽이나 가장 윗 방일 때만 다르게 처리해주면 된다.

 

 

<코드>

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
candy = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    for j in range(m):
        if i == 0 and j == 0:
            continue
        if i == 0:
            candy[i][j] += candy[i][j-1]
            continue
        if j == 0:
            candy[i][j] += candy[i-1][j]
            continue
        candy[i][j] += max(candy[i-1][j], candy[i][j-1], candy[i-1][j-1])
print(candy[-1][-1])