문제설명

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

• 입력
  • 첫째 줄에 테스트 케이스 T가 입력된다. (1 <= T <= 1,000)
  • 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력된다. (1 < n, m <= 20)
  • 매 테스트 케이스 둘째 줄에 n x m 위치에 매장된 금의 개수가 공백으로 구분되어 입력된다. (0 이상 10_텍스트_0 이하의 정수)
• 출력
  테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력한다.

접근

m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다.결과적으로 채굴자가 얻을 수 있는 금의 최대 크기...
매번의 선택에 따라 특정 위치에서의 누적값이 달라지고 이는 바로 직전의 누적값의 영향을 받음 => 큰 문제(금의 최대 크기)를 작은 문제(바로 직전의 금의 최대 크기)로 나눌 수 있음
특정 지점의 최댓값은 다음 지점의 최댓값에 영향을 줌 => 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일함

점화식
dp[i][j] = array[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])

풀이

for test_case in range(int(input())):
  n, m = map(int, input().split())
  array = list(map(int, input().split()))

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

for j in range(1, m):
  for i in range(n):
    # 왼쪽 위에서 오는 경우
    if i == 0:
      left_up = 0
    else:
      left_up = dp[i - 1][j - 1]
    # 왼쪽 아래에서 오는 경우
    if i == n - 1:
      left_down = 0
    else:
      left_down = dp[i + 1][j - 1]
    # 왼쪽에서 오는 경우
    left = dp[i][j - 1]
    dp[i][j] = dp[i][j] + max(left_up, left_down, left)

배운점

• 배열의 특정 구간을 규칙적으로 잡아 반복을 통해 2차원 DP를 생성할 수 있음
• 같은 들여쓰기의 if(else)문을 사용하여 따로 구해야할 결괏값을 각각 구할 수 있음