Chapter 8-3 개미 전사

< 이 글은 책 '이것이 취업을 위한 코딩 테스트다' 에서 발췌한 내용을 인용했습니다. >

 

개미 전사

 

<무지성 코드>

n = int(input())
foods = list(map(int, input().split()))
M = [0] * n

M[0] = foods[0]
M[1] = max(foods[0], foods[1])
for i in range(2, n):
    M[i] = max(M[i-2] + foods[i], M[i-1])

result = M[n]-1
print(result)

<답안 예시>

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

d = [0] * 100

d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
    d[i] = max(d[i-2] + array[i], d[i-1])

print(d[n-1])

 

거의 유사하다. 점화식만 잘 찾는다면 쉽게 풀 수 있는 문제이다.