이것이 코딩테스트다 - 15일차

주제

dynamic programming (동적 프로그래밍)

문제

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다.

메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다.

각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량 창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.

이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다.

따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.

예시

예를 들어 식량 창고 4개가 다음과 같이 존재한다고 가정하자

{1, 3, 1, 5}

이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다.

개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다.

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

조건

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

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

풀이 발상

언뜻 보면 짝, 홀과 같이 짝수번째 리스트를 더하고 홀수번째 리스트를 더하면 풀리는 문제같다.

하지만, 잘 생각해보자

현재 요소는 항상 현재인덱스 -2의 요소를 누적시킨 후 마지막에 있는 요소와 마지막 전에 있는 요소들 간 max값을 구하면 된다.

• 배열[현재인덱스] + 배열[현재인덱스 - 2]
• $f(2) = f(0) + f(2)$
• $f(3) = f(1) + f(3)$
• $f(4) = f(2) + f(4)$
• …

풀이 방법

1. 개미 전사 식량창고 N개의 갯수와 식량의 개수 리스트를 입력받는다.
2. 0, 1은 제외하고 (-2를 하면 음수가 되기때문) 배열[현재인덱스] + 배열[현재인덱스 - 2]를 누적한다.
3. 누적한 배열의 마지막 요소와 마지막 전 요소 중 큰 값을 찾아 출력한다.

n = int(input())
food_storage = list(map(int, input().split(' ')))

for i in range(2, n):
    food_storage[i] += food_storage[i - 2]

result = max(food_storage[n - 2], food_storage[n - 1])
print(result)

다른 풀이

• 점화식 : $a_i = max(a_{i-1}, a_{i-2} + k_i)$

1. 개미 전사 식량창고 N개의 갯수와 식량의 개수 리스트를 입력받는다.
2. memo배열을 식량창고 개수보다 크게 초기화한다.
3. memo[0], memo[1] (memo[1]은 memo[0]과 비교하여 둘 중 큰 값을 초기화한다) 배열을 초기화한다.
4. $a_i = max(a_{i-1}, a_{i-2} + k_i)$ 점화식을 사용한다.
5. memo배열의 마지막 요소를 출력한다.

n = int(input())
food_storage = list(map(int, input().split(' ')))
memo = [0] * 100

memo[0] = food_storage[0]
memo[1] = max(food_storage[0], food_storage[1])

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

print(memo[n - 1])