이코테-chapter8: 개미 전사

정리 내용

문제 설명

• 난이도: 중상
• 시간 제한: 1초
• 메모리 제한: 128mb
• 개미 전사는 식량창고를 공격하려하며 식량창고는 일직선으로 이어져있다.
• 식량창고 중에서 서로 인접한 식량창고가 공격을 받으면 바로 들킨다.
• 따라서 들키지 않으려면 최소한 한 칸 이상 떨어진 식량 창고를 약탈해야 한다.
• 첫째 줄에 식량창고의 개수 n이 주어진다. (3<=n<=100)
• 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 k가 주어진다.(0<=k<=1000)
• 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하라.
  ex) {1, 3, 1, 5} => 8

문제 풀이

• 왼쪽부터 차례대로 식량창고를 턴다고 가정하여 점화식을 세워보자.
• i번째 식량창고에 대한 최적의 해를 구할때 왼쪽부터 i-3 번째 이하의 식량 창고에 대한 최적의 해는 고려할 필요가 없다.
• 예를 들어 d[i-3]은 d[i-1]와 d[i-2]를 구하는 과정에서 이미 계산되었기 때문이다.
  1) i-1번째 식량창고를 털기로 결정한 경우 현재의 식량 창고를 털 수 없다.
  2) i-2번째 식량창고를 털기로 결정한 경우 현재의 식량 창고를 털 수 있다.
• 1와 2 중에서 더 많은 식량창고를 털 수 있는 경우를 선택하면 된다.
• 따라서, i번째 식량창고에 있는 식량의 양이 k(i)라고 했을 때, 점화식은 아래와 같다.
• a(i) = max(a(i-1), a(i-2) + k(i))

소스 코드

n = int(input())

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

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍 bottom-up
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])

출처 & 깃허브

이것이 취업을 위한 코딩 테스트다 with python

github