[다이나믹 프로그래밍] 개미 전사 - 파이썬(python)

개미 전사

난이도 : 中 풀이 시간 : 30분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

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

d = [0] * 100
d[0] = array[0]
d[1] = max(d[0], array[1])

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

print(d[n-1])

---

예시

 

# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
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])

---

해설

 

왼쪽부터 차례대로 식량 창고를 턴다고 가정하면 점화식을 세울 수 있습니다.
dp 테이블을 만들어 주고, d[i]에 대해서 d[i-1]과 d[i-2]와 array[i]를 더한 값을 대입해줍니다.