[Algorithm] 이것이 코딩 테스트다 - 개미 전사

교재 : 이것이 코딩 테스트다 with 파이썬
chapter 8 다이나믹 프로그래밍
실전문제 8-3 개미 전사 p.220
단순해 보이지만 점화식 처음에 점화식 세우기 어려움

개미 전사

문제

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

{1, 3, 1, 5}

이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다.

개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

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

출력

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

입력 예시

4
1 3 1 5

출력 예시

8

 

문제 해설

식량에서 개미 전사가 얻을 수 있는 최대 식량의 양을 구하는 문제이다. 최소한 한 칸 이상 떨어진 식량 창고를 선택해야 하고 이는 동적 계획법을 사용해 해결할 수 있다. 

주어진 N개의 식량 창고에 대해 각각의 식량을 약탈했을 때 얻을 수 있는 최대 식량의 양을 DP 테이블에 저장하면 된다. 

DP 테이블이 d [i]이고 i번째 식량 창고까지 고려했을 때 얻을 수 있는 최대의 양을 나타내면 된다.

 

왼쪽에서부터 차례대로 턴다고 생각하면 2가지 경우만 확인하면 된다.

1. i번째 식량 창고를 선택하지 않을 경우 

이전 식량 창고까지의 최대 식량의 양인 d [i-1]을 그대로 가져온다.

2. i번째 식량 창고를 선택하는 경우 

i번째 식량과 이전의 식량 창고까지의 최대 식량의 양인 d [i-2]를 더해서 가져온다. 인접합 식량 창고는 선택할 수 없기에 d[i-2]를 선택해야 한다.

 

한 칸 이상 떨어진 식량 창고로부터는 다 털 수 있으니까 i-3부터는 생각하지 않는다. 

따라서 DP 점화식은 다음과 같다.

d [i] = max(d [i-1], d [i-2] + 식량창고[i])

 

실행 코드

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

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 1 5

입력예시로 예를 들자면 d [0]=1 , d [1]=3

for i in range(2, 4):이고

• d [2] =max(3,1+1)
  • d [2]=3
• d [3]=max(3, 3+5)
  • d [3]=8

리스트는 0부터 시작이기에 d [n-1] 형태로 출력한다. 결과적으로 print(d [3]) => 8을 출력하게 된다.