[코테 스터디] DP, 금광

Q31. 금광

🐣문제

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

🐥풀이

오른쪽으로 금광을 캐가면서 금의 최대 크기로 업데이트 시켜간다.
최대값을 선택해 더해가면서 마지막에는 19가 젤 큰 것으로 확인 후 선택할 수 있다.


식으로 나타내면 a[n][m] = max(a[n-1][m-1], a[n][m-1], a[n+1][m])+a[n][m]이 될 수 있겠다. (물론 금광 내부의 인덱스여야 한다.)

🐓코드

for _ in range(int(input())):
  # 해당 케이스 입력값 받기
  n, m = map(int, input().split())
  input_val = list(map(int, input().split()))
  gold = [input_val[i:i+m] for i in range(0,n*m,m)]

  # dp 테이블
  dp = [[0]*m for _ in range(n)]
  for i in range(n):
    dp[i][0] = gold[i][0]
  
  for i in range(1,m):
    for j in range(n):
      if j-1<0:   # 왼쪽, 왼쪽 아래
        dp[j][i] = max(dp[j][i-1], dp[j+1][i-1])+gold[j][i]
      elif j+1>=n: # 왼쪽 위, 왼쪽 
        dp[j][i] = max(dp[j-1][i-1], dp[j][i-1])+gold[j][i]
      else:       # 왼쪽 위, 왼쪽, 왼쪽 아래
        dp[j][i] = max(dp[j-1][i-1], dp[j][i-1], dp[j+1][i-1])+gold[j][i]

  # 최대 결과값 구하기
  result = 0
  for i in range(n):
    # m번 움직이므로 dp에서 가장 오른쪽(m) 부분
    result = max(result, dp[i][-1])

  print(result)

⭐2022.05.06

DP의 기본을 배웠다!