[이코테] 다이나믹 프로그래밍_금광 (python)

문제

: 테스트 케이스 개수 t, n x m 크기의 금광.
첫번째 열의 어느 행에서든 시작해서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야함.
얻을 수 있는 금의 최대 크기는?

• 예시
  2
  3 4
  1 3 3 2 2 1 4 1 0 6 4 7
  4 4
  1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2

• 답
  19
  16

나의 풀이

1. 바텀업?(for문): 실패

import sys
input = sys.stdin.readline

d = [0] * 400 # 해당 칸까지 얻은 금의 양 표시

def gold_get(n, m, arr):
	# 0열의 값 기록
	for i in range(0, n * m, m):
		d[i] = arr[i]
        
	for j in range(n * m):
    	# 0열이 아닐 때
		if j % m != 0:
        	# 배열을 벗어난 경우 -1 나오도록(max시 선택되지 않도록)
        	# 오른쪽 아래로 내려온 경우
			down = d[j - m - 1] if j - m - 1 >= 0 else -1
            # 오른쪽으로 온 경우
            before = d[j - 1]
            # 오른쪽 위로 올라온 경우
			up = d[j + m - 1] if j + m - 1 < n * m else -1
            # 가장 많은 금을 캐온 이전 열 찾기 + 현재 칸의 금
			d[j] =  max(down, before, up) + arr[j]
    # 캘 수 있는 금의 최대치        
	return max(d)
     
t = int(input()) # 테스트 케이스 개수   

for i in range(t):
	n, m = map(int, input().split())
	gold = list(map(int, input().split()))
	print(gold_get(n, m, gold))
	d = [0] * 400 # d list 초기화

: 테스트 케이스 1은 성공했으나, 2가 자꾸 실패한다.
이유를 생각해보니..
d[j] = max(down, d[j - 1], up) + arr[j] 부분에서, up은 더 앞의 index 이므로 아직까지 d에서 0으로 기록되어 있기 때문인듯?
따라서 이번엔 재귀 함수로 돌려보자

2-1. 탑다운(재귀 함수): 왜 실패인가..

import sys
input = sys.stdin.readline

d = [0] * 400 # 해당 칸까지 얻은 금의 양 표시

def gold_get(n, m, x, arr):
	# 이미 계산된 칸인 경우, 그 값 리턴
	if d[x] != 0:
		return d[x]
        
	# 0열(각 행의 첫번째)의 값 기록
	if x % m == 0:
		d[x] = arr[x]
        
	if x % m != 0:
		# 배열을 벗어난 경우 -1 나오도록(max시 선택되지 않도록)
		# 오른쪽 아래로 내려온 경우
		down = gold_get(n, m, x - m - 1, arr) if x - m - 1 >= 0 else -1
		# 오른쪽으로 이동한 경우
		before = gold_get(n, m, x - 1, arr)
		# 오른쪽 위로 올라온 경우
		up = gold_get(n, m, x + m - 1, arr) if x + m - 1 < n * m else -1
        
		# 가장 많은 금을 캐온 이전 열 찾기 + 현재 칸의 금
		d[x] =  max(down, before, up) + arr[x]
        
	return max(d)
    
t = int(input()) # 테스트 케이스 개수   

for i in range(t):
	n, m = map(int, input().split())
	gold = list(map(int, input().split()))
	print(gold_get(n, m, n * m - 1, gold))
	d = [0] * 400 # d list 초기화

2-2. 탑다운: 2시간? 만에 성공~~

import sys
input = sys.stdin.readline

d = [0] * 400 # 해당 칸까지 얻은 금의 양 표시

def gold_get(n, m, x, arr):

	# 이미 계산된 칸인 경우, 그 값 리턴
	if d[x] != 0:
		return d[x]
        
	# 0열(각 행의 첫번째)의 값 기록
	if x % m == 0:
		d[x] = arr[x]
        
	if x % m != 0:
		# 배열을 벗어난 경우 -1 나오도록(max시 선택되지 않도록)
		# 오른쪽 아래로 내려온 경우
		down = gold_get(n, m, x - m - 1, arr) if x - m - 1 >= 0 else -1
		# 오른쪽으로 이동한 경우
		before = gold_get(n, m, x - 1, arr)
		# 오른쪽 위로 올라온 경우
		up = gold_get(n, m, x + m - 1, arr) if x + m - 1 < n * m else -1
	
		# 가장 많은 금을 캐온 이전 열 찾기 + 현재 칸의 금
		d[x] =  max(down, before, up) + arr[x]
        
	return d[x]
    
t = int(input()) # 테스트 케이스 개수   
result = []

# 테스트 케이스 개수만큼 for문이 돌도록
for i in range(t):
	n, m = map(int, input().split())
	gold = list(map(int, input().split()))
	
	# 끝 열마다 gold_get 함수값 얻도록
	for j in range(m - 1, n * m, m):
		 # 끝 열에 도달 했을 때 금의 양을 list에 저장
		result.append(gold_get(n, m, j, gold))
		d = [0] * 400 # d list 초기화
	
	print(max(result))