다이나믹 프로그래밍: 금광

문제정의

• n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져있으며, 각 칸은 특정한 크기의 금이 들어있습니다.
• 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m-1 번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야합니다.
• 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

입력조건

• 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (1 <= n, m <= 20)
• 둘째줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다. (1 <= 각 위치에 매장된 금의 개수 <= 100)

출력조건

• 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다.

입출력예시

#입력1
3 4
1 3 3 2 2 1 4 1 0 6 4 7
#출력1
19

#입력2
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
#출력2
16

정답코드

n, m = map(int, input().split())
array = list(map(int, input().split(" ")))

n = 3
m = 4
array = [1,3,3,2
        ,2,1,4,1
        ,0,6,4,7]

dp = []
idx = 0

for i in range(n):
  dp.append(array[idx:idx+m])
  idx += m

for j in range(1, m): # 두번째 열부터 마지막열까지
    for i in range(n): # 첫번째 행부터 마지막 행까지
        # 왼쪽에서 오는 경우
        left = dp[i][j - 1]

        # 왼쪽 위에서 오는 경우
        if i == 0 : left_up = 0 # 위쪽 벽 넘으면 0
        else: left_up = dp[i-1][j-1]

        # 왼쪽 아래에서 오는 경우
        if i == n-1 : left_down = 0 # 아래쪽 벽 넘으면 0
        else: left_down = dp[i+1][j-1]

        dp[i][j] = dp[i][j] + max(left_up, left_down, left)

result = 0
for i in range(n):
    result = max(result, dp[i][m-1])
print(result)

로직

• 금광의 모든 위치에 대해 다음 세가지만 고려합니다.

  1. 왼쪽 위에서 오는 경우
  2. 왼쪽 아래에서 오는 경우
  3. 왼쪽에서 오는 경우

• 받는 쪽의 관점으로 문제를 해석하고, 위 세가지 경우에서 가장 많은 금을 가지고 있는 경우를 dp 테이블에 갱신합니다.
• array에 있는 값을 dp[i][j]로 표현합니다.
• 점화식은 다음과 같습니다.
• dp[i][j] = dp[i][j] + max(dp[i-1][j-1], dp[i+1][j-1], dp[i][j-1])
• 테이블을 벗어나지 않는지 체크가 필요합니다.
• 편의상 초기 데이터를 담는 array변수를 사용하지 않고 dp 테이블을 활용해도 됩니다.