Hyuns Kim

Hyuns Kim

Learn, Run 👨‍💻🏃‍♂️

[이코테 2021] 개미 전사

[이코테 2021] 개미 전사

문제

책 : 이것이 코딩 테스트다. (220p)

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

{1, 3, 1, 5}

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

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

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

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

풀이

이 문제는 여러 반복된 연산 속에서 최대 값을 구하는 문제이다. 즉, dp를 활용하는 것이다.

결과를 두고 점화식을 알아보면,
d[1] 일 때, 최대값은 a[1] 이고
d[2] 일 때, 최대값은 max(a[1], a[2]) 이다.
d[3] 일 때, 최대값은 max(d[2], a[1] + a[3]) 인데,
이것은 max(d[2], d[1] + a[3]) 로 변경 가능하다.
d[4] 일 때, 최대값을 max(d[3], a[2] + a[4]) 인데,
이것은 max(d[3], d[2] + a[4]) 로 변경 가능하다.


즉, n에서의 최대 값은, d[n] = max(d[n-1], d[n-2]+a[n]) 으로 나타낼 수 있다.
이것을 그대로 코드로 나타내면, 다음과 같다.
0, 1은 처음에 정해준다.

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

def solution(n, array):
    d = [0] * (n)
    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])

solution(n, array)

실수 및 배운 점

  • 점화식을 구할 때, 쪼는 것부터 시작된 것 같다.
    예를 들면서 논리적으로 구해봐야겠다.

참고