[알고리즘] 개미전사

개미전사 문제

개미 전사는 부족한 식량을 충당 하고자 메뚜기 마을의 식량창고를 공격하려고 한다. 식량착고는 일직선으로 이어져 있는데 개미전사는 한칸 떨어진 식량 창고를 약탈해야 한다.

예시

[1, 3, 1, 5] ==> 8

입력 조건

3 <= N <= 100
0 <= K <= 1000

출력 조건

개미 전사가 얻을 수 있는 식량의 최댓값

체크해야할 점

완전 탐색으로 해결이 가능한 문제인가?
해결이 어려울 것 같다. 구체적으로 길이가 n 일때 우리가 탐색해야할 가짓수는 2^n이 되므로 이 문제는 확실시 다이나믹 프로그래밍이 필요해 보인다.

다이나믹 프로그래밍을 활용하기 위해 체크해야 할 점

1. 큰 문제를 작은 문제로 나눌 수 있는가?
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일한가?

해결과정을 도식화 하는 과정은 매우 중요하다. 때문에 도식화 하는 과정을 거치는 것이 추후 코드를 구성할 때 아주 강한 힘이 된다.

코드 구현

N = int(input())
num_list = list(map(int, input().split()))

def ant(nums: list[int]) -> int:
    memo = [0]*len(nums)
    for i in range(0, len(nums)):
        if i == 0:
            memo[i] = nums[i]
        elif i == 1:
            memo[i] = max(nums[i], memo[i-1])
        # 3이상부터 점화식을 적용하자.
        else:
            memo[i] = max((nums[i] + memo[i-2]), memo[i-1])
    return memo[-1]

print(ant(num_list))