이코테 Chapter 08 - 개미 전사

문제

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

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

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

 

입력

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

출력

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

---

접근법

1. 문제를 보고 탐색으로 푸는거구나 생각했다.

2. 조건을 걸어 인접한 창고는 탐색하지 못하게해서 하면 되겠구나 생각함

3. 그리고 첫번째 창고를 탐색하고 세번째 창고를 탐색하는거나 세번째 창고를 탐색하고 첫번째 창고를 탐색하는게 같으니 이런 경우에는 리스트에 저장해 불필요한 계산을 막아야겠다 생각함

4. 반복문(while문)을 통해 탐색하는 인덱스가 n을 넘어가면 반복을 종료하면 되겠구나하고 호기롭게 코딩 시작..

 

[소스 코드]

사실 이번 문제는 내가 접근한 방법으로 풀려니깐 생각보다 많이 복잡해서 아무리 생각해도 이렇게 푸는게 아닌거같다 생각해서 30분정도 풀다가 책을 보니깐 보텁업 방식을 이용해 점화식으로 프로그래밍했더라...그래서 책보고 이해하는식으로 문제를 마쳤다.

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

d = [0] * 100

d[0] = array[1]
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])

 

오답노트

- 일단 문제를 볼 때 현재 내가 다이나믹 프로그래밍을 배우고 있다는 걸 알고 있었지만 그런것을 뒤로한채 그냥 생각의 흐름대로

문제를 어떻게 풀지 생각하다보니깐 못 푼거 같다. 문제를 일단 딱 보면 어떤 식으로 풀어야할지 정확히 판단하고 풀어야겠다..