(Python) 다이나믹 프로그래밍(DP) 실전 문제 - 개미 전사

본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임

문제

풀이

현재 i번째 식량창고에서 i-1번째와 i-2번째를 확인해가며 진행해가므로 DP로 문제를 푼다.

왼쪽부터 차례대로 식량창고를 턴다고 생각하자.

i-3번째 이하의 식량창고에 대해서는 고려할 필요가 없다. 한 칸 이상 떨어진 식량창고는 항상 털 수 있기 때문이다. 이전의 각 식량창고에서 얻을 수 있는 최대 식량을 DP리스트에 저장해가며 진행할 것이다.

소스코드

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

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

# 다이나믹 프로그래밍( Dynamic Programming ) 진행(보텀업)
d[0] = arr[0]
d[1] = max(arr[0], arr[1])
for i in range(2, n):
    d[i] = max(d[i-1], d[i-2] + arr[i]) 

# 계산된 결과 출력
print(d[n-1])