다이나믹 프로그래밍 기법
한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법.

탑다운 방식
재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
바텀업 방식
반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식

✅ 문제

개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

입력 예시

4
1 3 1 5

출력 예시

8

💻 코드

N = int(input())

input_data = list(map(int, input().split()))

d = [0] * (N + 1)

d[1] = input_data[0]
d[2] = input_data[1]

for i in range(3, N + 1):
    max_val = 0
    for j in range(i - 2, 0, -1):
        temp = d[j] + input_data[i-1]
        max_val = max(max_val, temp)
    d[i] = max_val

print(max(d[-1],d[-2]))

설계

바텀업 방식을 이용하여 리스트 d에 그 인덱스만큼의 식량창고에 도달할 때 약탈할 수 있는 최대한의 식량을 계산하여 저장한다.
마지막 또는 마지막 바로 앞의 식량창고까지 도달할 때 최대값을 구할 수 있으므로 둘 중 최대값을 출력한다.

➕ 다른 풀이

여기서 리스트 d는 리스트에 순차적으로 그 인덱스까지 도달했을 때, 입력된 리스트의 값에 상관없이 최댓값을 저장해 놓았다. 나는 리스트 d에 그 인덱스까지 도달했을 때, 입력된 리스트의 그 인덱스가 가질 수 있는 최대값을 구했다.

N = int(input())

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

d = [0] * 100

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])

📝 정리

문제를 풀었다고 해도 다른 풀이를 꼭 봐야겠다. 더 효율적인 답이 나오네..