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

개미 전사

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

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

 

---

 

해답

 

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

dp_table = [0] * 100

dp_table[0] = foods[0]
dp_table[1] = max(foods[0], foods[1])
for i in range(2, n):
    dp_table[i] = max(dp_table[i-1], dp_table[i-2] + foods[i])

print(dp_table[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])

 

---

해설

 

문제를 풀기 위한 아이디어가 중요합니다.
i번째 식량 창고를 털 경우에, (i-2번째 식량 + i번째 식량)을 더한 합과 i-1번째 식량을 선택했을 때의 합을 비교하여 더 큰 경우를 선택해야 합니다.
다이나믹 프로그래밍 알고리즘 문제는 그림을 그려 이해하는게 쉬워 보입니다.
코드는 n과 foods에 입력을 받고, dp 테이블을 생성해줍니다.
0과 1번 칸에는 초기값을 생성해주고, for 반복문에서 위에 설명한 아이디어를 적용하여 dp 테이블과 foods 리스트를 비교하여 답을 구할 수 있습니다.