[이것이 코딩테스트다] 개미 전사 (DP/Python)

문제

개미 전사는 메뚜기 마을의 식량창고를 몰래 공격하려고 한다.
메뚜기 마을의 식량창고는 일직선으로 되어 있는데 식량창고는 일직선으로 이어져있다.
각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.
메뚜기 정찰병은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.

개미 전사는 식량창고 N에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하라.

예를 들어 식량창고 4개가 아래와 같이 존재한다고 가정하자.

[1,3,1,5]

이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 ㄸ ㅐ최댓값인 총 8개의 식량을 빼앗을 수 있다.

---

입력 조건

- 첫째 줄에 식량창고의 개수 N이 주어진다(3 <= N <= 100)

- 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다(0 <= K <= 1000)

 

출력 조건

- 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

---

입력 예시                                    출력 예씨

4                                                     8

1 3 1 5

 

---

다이나믹 프로그래밍이라는 걸 보면 겁부터 먹고 시작하는데 이번엔 순조롭게 풀 수 있었따!!!!!!!!!

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

res = [0] * n
res[0] = arr[0]
res[1] = max(arr[0],arr[1])
for i in range(2,n):
    res[i] = max(res[i-2]+arr[i],res[i-1])

print(res[n-1])

res[1] = arr[1]을 넣었었는데 저기에도 max 함수를 이용해서 정해야 한다는 사실은 답지를 보고 알았다

---

 

 

고민의 흔적.. 

N 이 3부터 시작하기 때문에 f(3)부터 생각을 했다.

f(3)일 때 1+3을 골랐으면 f(4)일땐 어떻게 2를 골라와서 2+4를 하지? 두개를 모두 저장해놔야 하나?

(추가로 f(4)일 때 1+4도 가능했당.....)

 

고민을 엄청 하다가 돌아가기로 마음 먹고 f(1)부터 생각을 해보니 곧바로 해답을 알 수 있었다!

항상 최대값을 저장해둔다면 다음과 같은 점화식을 얻을 수 있다

f(i) = max(f(i-2)+arr[i],f(i-1))

 

하하 쉬운 문제도 아직은 버겁지만 열심히 해야겠당.