[Python] 이것이 코딩테스트다 with 파이썬 - 개미 전사 - 다이나믹 프로그래밍 (DP)

해당 문제 및 해설은 "이것이 코딩테스트 다 with 파이썬" 책을 기준으로 요약 및 정리하여 작성하였습니다.

 

이것이 코딩테스트다 with 파이썬 구입처

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

 

---

문제 : 개미 전사

 

개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이 때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에서 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량 창고 4개가 다음과 같이 존재한다고 가정해보자.

 

{ 1 , 3 , 1 , 5 }

1

3

1

5

 

이 때, 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다. 개미 전사를 위해 식량창고 N 개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성해보자.

 

입력 조건

• 첫째 줄에 식량창고의 개수 N 이 주어진다. ( 3 ≤ N ≤ 100 )
• 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수가 K가 주어진다. ( 0 ≤ K ≤ 1,000 )

 

출력 조건

• 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

 

입력 예시	출력 예시
4 1 3 1 5	8

 

문제 해설

위의 예시를 보고, 경우의 수를 다음 그림 처럼 그린다면 8 가지가 나온다.

개미 전사 경우의 수

동적 프로그래밍 ( DP ) 의 핵심 중 하나는 점화식을 어떻게 만드는 가 ? 가 중요하다.

특정한 i 번째 식량창고에 대해서 털지 안 털지의 여부를 결정할 때, 단 2가지 경우에 대해서만 확인하면 된다.

 

점화식 경우의 수

위의 두 가지 경우의 수중 하나를 선택하면 된다.

 

코드

import sys

input = sys.stdin.readline

# 정수 N을 입력받기
n = int(input())

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

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

# 다이나믹 프로그래밍(DP) 진행 (바텀업)
dp[0] = array[0]
dp[1] = max(array[0], array[1])

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

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

 

주의할 점 

앞서 말씀 드린 문제인 DP 의 경우, 점화식으로 문제를 푸는 것이 굉장히 중요하다. 다만, 초기 DP 테이블을 만들 때 N 개를 생성할 것인지, 배열에 성질에 따라 N + 1 개를 만들 것인지 헷갈릴 가능성이 많다. 천천히 자기만의 규칙을 만드는 것이 중요하다고 생각한다.