[이코테] 다이나믹 프로그래밍_개미 전사 (python)

문제

: 일직선 상에 존재하는 식량창고.
개미 전사가 식량을 터는데..!
문제는 최소 1칸 건너뛰어서 식량을 털어야함.
이때, 털 수 있는 식량의 최대치는?

• 예시:
  4
  1 3 1 5

• 정답:
  8

나의 풀이

1-1. 탑다운 방식(재귀 함수) -> 오류 발견!

import sys
input = sys.stdin.readline
n = int(input())
food = list(map(int, input().split()))

d = [0] * n

def ant(x, num):
	# index가 0, 1 일때 값 설정
	d[0] = num[0]
	d[1] = max(num[0], num[1])
	
	# 함수에 x를 입력하는데 왜 x-1을 사용하나?
	# : 끝 index가 x-1이기 때문에
    
	# 이미 계산한 적 있다면, 그 값 그대로 리턴
	if d[x - 1] != 0:
		return d[x - 1]
        
	# 한 칸 이전까지의 총 식량과 
	# 두 칸 이전까지의 총 식량 + 현재 칸의 식량을 더한 값 중에서 큰 값을 선택
	d[x - 1] = max(d[x - 2], d[x - 3] + num[x - 1])
	return d[x - 1]
    
print(ant(n, food))

: 재귀 함수가 작동을 하지 않는다! 오류 발견!!

1-2. 오류 수정: 이제서야 재귀 함수가.. 작동을..

import sys
input = sys.stdin.readline
n = int(input())
food = list(map(int, input().split()))

d = [0] * n

def ant(x, num):
	# index가 0, 1 일때 값 설정
	d[0] = num[0]
	d[1] = max(num[0], num[1])
	
	# 함수에 x를 입력하는데 왜 x-1을 사용하나?
	# : 끝 index가 x-1이기 때문에
    
	# 이미 계산한 적 있다면, 그 값 그대로 리턴
	if d[x - 1] != 0:
		return d[x - 1]
        
	# 한 칸 이전까지의 총 식량과 
	# 두 칸 이전까지의 총 식량 + 현재 칸의 식량을 더한 값 중에서 큰 값을 선택
	d[x - 1] = max(ant(x - 1, num), ant(x - 2, num) + num[x - 1])
	return d[x - 1]
    
print(ant(n, food))

d[x - 1] = max(d[x - 2], d[x - 3] + num[x - 1]) 부분을
-> d[x - 1] = max(ant(x - 1, num), ant(x - 2, num) + num[x - 1]) 로 수정 완료!
재귀 함수니까 함수명을 써야했는데, d list를 썼지 뭐야~! 근데도 테스트 케이스가 통과한 이유는 테스트 케이스의 원소가 적어서!

2. 바텀업 방식

import sys
input = sys.stdin.readline

n = int(input())
food = list(map(int, input().split()))

d = [0] * n

# index가 0, 1 일때 값 설정
d[0] = food[0]
d[1] = max(food[0], food[1])

# 탑다운과는 다르게 range가 n - 1까지 범위이므로
# 굳이 최대치를 x - 1로 설정 안해도 됨
# d[0], d[1]을 위에서 선언 했으므로 2부터 시작
for x in range(2, n):
	# 한 칸 이전까지의 총 식량과 
	# 두 칸 이전까지의 총 식량 + 현재 칸의 식량을 더한 값 중에서 큰 값을 선택
	d[x] = max(d[x - 1], d[x - 2] + food[x])
    
# 끝 index 는 n - 1 이므로
print(d[n - 1])