금광 - dp

시간이 남아서 DP문제를 한문제 더 풀어보았다.

아주 간단한 DP문제이다 

각 합들이 최대가 되는 DP테이블을 만들어서 풀면 된다. 

시간이

1. 각 입력을 2차원 배열로 바꿔서 저장한다.

2. 누적합을 계산할 테이블(GOLD)를 생성한 후 첫째줄은 입력받은 값과 동일하게 설정 해준다

3. 맨 윗줄일 경우 우,우상 으로 이동해서 계산하는 방법뿐이고 맨 아랫줄의 경우 우, 우하 로 이동해서 계산하는것뿐이므로 분기를 나누어준다. 그 외에는 우 우상 우하 로 이동하면서 계산 할 수 있다.

4. 최종적으로 계산된 GOLD테이블의 마지막줄에서 최댓값을 출력해주면 된다.

import sys
sys.stdin = open("/Users/positive/Desktop/무제 폴더/Algorithm/230105/goldin.txt","r")
input = sys.stdin.readline
def gold(n,m,arr):
  MAP = []
  GOLD = [[0 for i in range(m)]for i in range(n)]
  for i in range(n):
    MAP.append(arr[i*m:i*m+4])
  for i in range(n):
    GOLD[i][0] = MAP[i][0]
  
  for j in range(1,m):
    for i in range(n):
      if i == 0:
        GOLD[i][j] = max(GOLD[i][j-1]+MAP[i][j],GOLD[i+1][j-1]+MAP[i][j])
      elif i == n-1:
        GOLD[i][j] = max(GOLD[i-1][j-1]+MAP[i][j],GOLD[i][j-1]+MAP[i][j])
      else:
        GOLD[i][j] = max(GOLD[i-1][j-1]+MAP[i][j],GOLD[i][j-1]+MAP[i][j],GOLD[i+1][j-1]+MAP[i][j])
  answer=0
  for i in range(n):
    if GOLD[i][-1] >answer:
      answer = GOLD[i][-1]
  print(answer)
T = int(input())
for _ in range(T):
  N,M = map(int,input().split())
  ARR = list(map(int,input().split()))
  gold(N,M,ARR)