개미 전사 [dynamic Programming] #이것이 코딩테스트다

[문제] 1로 만들기: 문제 설명

개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다.메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다.각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다.따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.
{1, 3, 1, 5}
이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다.개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다.개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

난이도: ●●○| 풀이시간 20m | 시간제한 1초 | 메모리 128mb

 

<input case>

첫째 줄에 식량창고의 개수 N이 주어진다. (3<=N<=100)
둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0<=K<=1,000)

 

 

<Output case>

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

input example	Output example
4 1 3 1 5	8

<Idea>

Q1. 응어어엄ㅁ어ㅓㅁㅇ머 이게 뭐야 이게 규칙성이 있나?
A 정신차려 친구 다이나믹 프로그래밍은 그리디 알고리즘의 연장선이야 작은 수부터 천천히 해결해나가면 되는거야
Q2. 아 맞아 그럼 작은 수부터 천천히 계산 ->  리스트에 넣기를 반복해나가면 되는거였지 근데 예는 바로 옆에게 아닐 수도 있잖아
A. 그치 그래서 문제가 조금 직관적이지 못해 그래서 값을 그대로 받지 않고 그 전 값이 더 크면 그 전 값을 그대로 받고 있을거야 그럼 그 다음 케이스에선 무조건 더해지겠지?
Q3. 아 무슨 이야기인지 알았어

 

n=int(input())
data=list(map(int,input().split()))
d=[0]*(n+2)

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

print(d)