개미 전사

1. 문제 설명

출처 : 이코테2021

---

2. 문제 조건

---

3. 문제 해결 아이디어

• N = 4일 때, 다음과 같은 경우들이 존재할 수 있다.
• 식량을 선택할 수 있는 경우의 수는 다음과 같이 8가지이다.
• 7번째 경우에서 8만큼의 식량을 얻을 수 있으므로 최적의 해는 8이다.

 

• i는 인덱스이므로 0부터 시작한다.
• 창고 0만 있을 때는 a(o) = 1이 최대 값
  • 창고 0,1만 있을 때는 a(1) = 3이 최대 값
  • 창고 0,1,2만 있을 때는 a(2) = 3이 최대 값
  • 모든 창고일때는 창고1, 3 = 8이 최대 값
• 이렇게 DP 테이블 값을 재정의한다.

 

• 왼쪽부터 차례대로 식량창고를 턴다고 했을 때, 특정한 i번째 식량창고에 대해서 털지 안 털지의 여부를 결정
• 위 2가지 경우 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다.
• 즉, i번째는(현재식량창고)는 i-1과 i-2 이 2개를 비교해서 결정할 수 있다.
  • i-1에서 식량을 털었으면 i는 털 수 없다.
  • 즉! i-1까지의 최적의 해 VS i-2 + i(현재식량창고)까지의 최적의 해의 합 비교를 진행한다.
• 다이나믹 프로그래밍을 쓸 수 있는 이유는 큰 문제(현재 식량 창고)를 풀기 위해 작은 문제 i-1, i-2를 비교해서 가능

 

• 점화식
  • a(i)의 최대 값은 (a(i-1), a(i-2) + k) 값을 비교해서 큰 값을 선택

---

4. 답안

n = int(input())

#모든 식량 정보 입력
array = list(map(int, input().split()))

#DP 테이블 초기화
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 - 1], d[i - 2] + array[i])

print(d[n-1])

#출력 결과
4
1 3 5 8
11