개미 전사-[이것이 취업을 위한 코딩 테스트다]

📖 문제

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

{1, 3, 1, 5}

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

입력 조건

첫째 줄에 식량창고의 개수 N이 주어진다.(3 <= N <= 100)

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

출력 조건

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

Answer

# 개미 전사: 답안

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

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
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])

이번 문제도 다이나믹 프로그래밍을 이용한 문제였고, bottom up 방식을 이용하여 푸는 문제였다. 

우선 dp는 규칙을 이해해야 했다. 우선 간단하게 생각해보면 문제 조건에 의하여 바로 이전 칸을 선택했으면 이번 칸은 선택하지 못한다. 따라서 바로 이전칸을 방문했을 때와 이전칸을 방문하지 않을 때의 식량 총합을 비교해서 더 큰 선택을 해야한다. 

우선 첫번째 식량창고의 경우 비교할게 없으므로 그대로 array[0]을 넣어준다. d[1]=두번째 식량창고의 경우, 

이전 식량 창고를 선택했을 경우와 선택하지 않고 이번 식량창고를 선택하는 array[0]과 array[1]을 비교해줘야한다. 

이후 세번째 식량창고부터는 바로 전을 선택해서 이번 창고를 선택하지 않는경우 vs 바로 전을 선택하지 않고 이번 창고를 선택하는 경우를 비교하며 더 큰 값으로 갱신해가면 된다. 이렇게 갱신할경우 마지막 d[n-1]에 최적의 값이 저장되게 된다.