다이나믹 프로그래밍 연습문제 - 개미 전사

🍎 개미 전사

 

🏀 문제

(문제 요약)

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다.

식량 창고는 일직선으로 이어져 있다.

개미 전사는 식량창고를 선택적으로 약탈할 것이다.

인접한 식량 창고가 공격을 받으면 메뚜기 정찰병들에게 들킨다. 

개미 전사는 정찰병에게 들키지 않고 최대한 많은 식량을 얻기를 원한다.

 

⚾ 코드

n = int(input())
store = list(map(int, input().split()))
dp = [0]*n

dp[0] = store[0]
dp[1] = max(store[0], store[1])

for i in range(2, n):
    dp[i] = max(dp[i-1], dp[i-2]+store[i])

print(dp[n-1])

 

🔔 해결 과정 & 깨달은 점

- DP 테이블에 저장되는 것은 앞에서부터 보았을 때 가장 많이 약탈할 수 있는 식량의 개수이다.

- 바로 옆의 창고는 약탈할 수 없으므로, (전전 창고까지 얻을 수 있는 식량의 개수 + 현재 위치의 식량 개수) 와 (전 창고에서 얻을 수 있는 식량의 개수) 중에 최대 값을 현재 창고까지 왔을 때 얻을 수 있는 식량의 개수의 최댓값이라고 할 수 있다.

 

- 사실 6개월 전쯤에 이 문제를 풀었을 때는 잘 이해가 되지 않아 풀지 못했다. 그러나 시간이 지나 다시 풀어보니 생각보다 쉽게 풀렸다. 개념을 더 이해하고 있기 때문일지도 모른다. 이해 하지 못하는 문제가 와도 당황하지 않고 개념을 익히며 풀면 풀 수 있다는 자신감을 얻고 있는 중이다!

 

---

출처

📚 이것이 취업을 위한 코딩 테스트다 with 파이썬