[이코테] CH08 다이나믹 프로그래밍 실전문제 31번 금광

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def findMax(element):
   arr = [[0 for _ in range(m)] for _ in range(n)]
   
   index = 0

 
   maxarray =[]
   for i in range(n):
    for j in range(m):
     arr[i][j] = (element[index])
     index +=1
   print(arr)
   for i in range(n):
      d = [0] * (m+1)
      d[0] = arr[i][0]
      row = i 
      for j in range(m-1):
        if row == 0: # 선택지가 오직 오른쪽과 오른쪽 아래만 있는 경우
          if arr[row+1][j+1] > arr[row][j+1]: 
            row +=1
          d[j+1] =  d[j] + arr[row][j+1]
        elif 1<=row<n-1:
          if arr[row+1][j+1] > arr[row-1][j+1] and arr[row+1][j+1] > arr[row][j+1]:
            row +=1
          elif arr[row-1][j+1] > arr[row][j+1] and arr[row-1][j+1] > arr[row+1][j+1]:
            row -=1
          d[j+1] =  d[j] + arr[row][j+1]
        elif row == n-1:
          if arr[row-1][j+1] > arr[row][j+1]:
            row -=1
          d[j+1] =  d[j] + arr[row][j+1]
      maxarray.append(max(d))
   return max(maxarray)
          


T = int(input())
n,m = map(int,sys.stdin.readline().split())



element1 = list(map(int,sys.stdin.readline().split()))
print(findMax(element1))
n,m = map(int,sys.stdin.readline().split())
element2 = list(map(int,sys.stdin.readline().split()))
print(findMax(element2))

답지랑 좀 다르게 풀었다

일단 DP 테이블을 일차원배열로 선언했다

최댓값을 찾아야하는데 시작점을 각 0열의 원소들을 기점으로 잡아서

그중 최댓값을 잡아야한다고 생각했다

 

그래서 , 처음 d[0] = arr[i][0]로 잡았다(이러면 순서대로 시작점이 잡히므로)

여기서부터 오른쪽 위, 오른쪽, 오른쪽 아래

이때 나의 행이 맨 위거나 맨 아래라면 , 오른쪽 위 /오른쪽 아래는 제외할 수 있도록 코드를 짰다.

이렇게 Bottom - up 방식으로 0,1,2,3...n-1열까지 탐색하면서 최댓값이 어딘지를 찾을 수 있는 코드를 짰다

생각은 났지만 생각보다 코드로 옮기는게 어려웠다

 

그래도 답지 하나도 안 보고 혼자 다 풀어내서 뿌듯한 하루 !