[알고리즘] 개미 전사 (DP-이코테)

문제 유형 : 다이나믹 프로그래밍

 

문제 설명(요약) :

최소한 한 칸 이상 떨어진 인덱스의 요소들을 합하여 나가는 과정 후

최댓값을 구하는 문제

 

접근 :

{3, 5, 4, 5, 6, 8, 4} 예제 케이스 만들기

현재 인덱스의 요소는 -2칸 or -3칸 떨어진 인덱스의 요소로부터 올 수 밖에 없음

최댓값을 구하기 위해선 -2칸 or -3칸 떨어진 인덱스와 현재 값과의 합중 최댓값으로 갱신되어야 함

 

점화식 추론 :

A[i] = max(A([i-2] + A[i]),(A[i-3]  + A[i]))

 

결론 :

dp 리스트의 마지막 인덱스와 그 전 인덱스 중 최댓값을 구하면 원하는 답을 구할 수 있음

 

코드 구현 :

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

dp[2] = dp[0] + dp[2]

for i in range(3,len(dp)):
    dp[i] = max((dp[i-2] + dp[i]),(dp[i-3] + dp[i]))


print(max(dp[i-1],dp[i]))

 

풀이 노트 :