[BOJ/Python] 이동하기 || 다이나믹 프로그래밍

백준 이동하기 파이썬 11048

11048번: 이동하기

❍ 문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

❍ 입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

❍ 출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

 

❏ 문제 풀이

❍ 풀이

이동은 오른쪽, 아래, 오른쪽 + 아래(대각선)으로 이동이 가능하다.
누적으로 합을 구하게 되어 최종적으로 가장 크게 가져올 수 있는 사탕 개수를 구해야 하는데, DP 2차원 리스트를 생성하여 이를 체크해주도록 하였다.
먼저, dp[i][j]는 (i, j)에서 가질 수 있는 가장 많은 사탕의 수를 의미한다. 해당 칸에서 가질 수 있는 최대의 사탕 수를 구하기 위해선, (-1, 0), (-1, -1), (0, -1)에서의 사탕 수 중 가장 많은 사탕 수에 현재 해당 칸의 사탕 수를 합하면 된다.
이동이 가능한 오른쪽, 아래, 오른쪽 + 아래(대각선)의 반대인, 왼쪽, 위, 왼쪽 + 위(대각선)의 사탕 개수를 비교해주면 된다.
즉, 점화식은 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + (i, j)의 사탕수 가 된다.
 
표를 함께 살펴보자면, 아래와 같이 사탕이 주어졌을 때,

1	2	3
9	8	7
4	5	6

 
이와 같은 dp 리스트가 생성되게 된다. 최종적으로 dp[n - 1][m - 1]이 결과값이 된다.

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

 

❍ CODE

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
candy = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(m)] for _ in range(n)]
direction = [(-1, 0), (-1, -1), (0, -1)]
for i in range(n):
    for j in range(m):
        max_candy = 0
        for dx, dy in direction:
            ni = i + dx
            nj = j + dy
            if ni >= 0 and ni < n and nj >= 0 and nj < m:
                max_candy = max(max_candy, dp[ni][nj])
        dp[i][j] = max_candy + candy[i][j]

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

왼쪽, 위쪽, 왼쪽 + 위쪽(대각선) 중 가장 큰 사탕 수를 찾고, 거기에 (i, j)의 사탕 수를 합해준다.
 

❍ CODE

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
candy = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
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 리스트를 구현할 때, 이전에 구해둔 값을 재활용하는 경우가 많기 때문에, 위처럼 인덱스를 0부터가 아닌 1부터 시작하도록 하면 더 코드가 간결해지는 것 같다.