[이것이 코딩 테스트다] 개미 전사 with Python

🔒 문제

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

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

입력

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

4 1 3 1 5

출력

8

✅ 해설

• 식량의 최댓값을 저장하는 배열 d
  • 만약 d[3] = 5 라면, 식량 창고가 3개일 때, 얻을 수 있는 최고 식량이 5임을 의
  • 만약 식량 창고가 3개이며, 식량 개수가 각각 [ 1 ][ 2 ][ 4 ] 라면
    • d[1] = 1
    • d[2] = 2
    • d[3] = 1 + 4 = 5 이다.
  • 위와 같은 원리로 식량 창고 개수가 1개일 때부터 n개일 때까지 얻을 수 있는 식량의 최댓값을 저장하며 계산한다.
    • 중요한 것은 n 번째의 최대 식량을 구하기 위해 1부터 (n-1)까지 최대 식량을 전부 구해 저장해야 한다는 것이다.
• 식량 창고를 연속해서 털 수 없으므로, 두 가지 경우를 고려하여 더 큰 이득을 주는 쪽을 선택한다.
  • 첫 번째 경우, i 번째 식량 창고를 털지 않을 때
    • i 번째 식량 창고를 털지 않는다는 것은 d[ i - 1] + 0 을 의미한다.
  • 두 번째 경우, i 번째 식량 창고를 털 때
    • i 번째 식량 창고를 턴다는 것은 d[ i - 2 ] + (i 번째 식량) 을 의미한다.
    • d[ i - 1] + (i 번째 식량)이 될 수 없는 이유는 연속해서 창고를 털 수 없기 때문이다.
  • 따라서 위를 코드로 표현하면 아래와 같다.

    # i번째 식량 창고를 털 때
    candi1 = d[i-2] + storage[i]
    # i번째 식량 창고를 털지 않을 때
    candi2 = d[i-1]
    # 더 큰 값을 선택하기
    d[i] = max(candi1, candi2)

💻 코드

# 식량 창고 개수 입력받기
n = int(input())

# 식량 창고 정보 입력받기
storage = list(map(int, input().split()))

# 식량의 최댓값을 저장하는 배열 d
d = [0] * n
d[0] = storage[0]
d[1] = max(storage[0], storage[1])

# 식량의 최댓값 구하기
for i in range(2, n):
    # i번째 식량 창고를 털 때
    candi1 = d[i-2] + storage[i]
    # i번째 식량 창고를 털지 않을 때
    candi2 = d[i-1]
    # 최댓값 찾기
    d[i] = max(candi1, candi2)

print(d[n-1])