[Baekjoon] DP - 11048 이동하기

문제

https://www.acmicpc.net/problem/11048

 

풀이

큰 문제를 작은 문제로 나누어 풀 수 있는 DP 문제이다.

 

D[N][M]: (N, M) 위치에 있을 때, 사탕을 최대한 많이 가져올 수 있는 개수

 

1. 첫 블럭 예외 (첫 블럭이 곧 사탕 최대 개수)

2. i 열이 0인 경우 첫 블럭부터 계속 쌓아온 사탕 개수

3. j 열이 0인 경우 첫 블럭부터 계속 쌓아온 사탕 개수

4. 대각선인 경우 아래 경우의 수 중 가장 큰 사탕 개수

  4-1) 위에서 온 경우

  4-2) 왼쪽에서 온 경우

  4-3) 대각선에서 온 경우

예시

3 x 4

사탕 수

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

 

최대 개수

1	3	6	10
1	3	6	15
10	18	25	31

 

코드

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
d = [[0] * m for _ in range(n)]
a = []
for _ in range(n):
    a.append(list(map(int, sys.stdin.readline().rstrip().split())))

for i in range(n):
    for j in range(m):
        if i == 0 and j == 0:
            d[i][j] = a[i][j]
            continue

        if i == 0:
            d[i][j] = d[i][j - 1] + a[i][j]
            continue

        if j == 0:
            d[i][j] = d[i - 1][j] + a[i][j]
            continue

        d[i][j] = max(d[i][j - 1], d[i - 1][j], d[i - 1][j - 1]) + a[i][j]

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