개미 전사

이것이 코딩테스트다. 220페이지 문제이다.

스키장 3,5,7일권 최저가 구하기 문제와 비슷하다.

다이나믹프로그래밍의 정석 문제 같다.

다이나믹 프로그래밍은 보통 min(나올수있는 경우들) 또는 max(나올 수 있는 경우들)을 이용한다.

이 문제는 바텀업방식문제이다.

구상단계의 스케치

아래는 나의 코드이다.

 

import sys

N=int(sys.stdin.readline().rstrip())
food = list(map(int,sys.stdin.readline().split()))

dp=[0]*N
dp[0]=food[0]
dp[1]=max(food[0],food[1])

for i in range(2,N):
    dp[i] = max(dp[i-2]+food[i],dp[i-1])
print(dp)
print(dp[N-1])

 

아래는 예시 코드이다.

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

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
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])