DP - 개미 전사

DP(Dynamic Programming) 기법
해결한 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 캐싱 기법을 활용하여 문제의 시간 복잡도를 줄이는 문제 해결 기법. -> 탑다운(재귀함수),바텀업(반복문) 활용 가능

• DP -> 점화식 활용하기 (규칙성 찾기)

✅ 문제

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

입력 예시
4
1 3 1 5

출력 예시
8

💻 코드

import java.util.*;

public class DP_Exercise1
{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        ArrayList<Integer> arrayList = new ArrayList<>();

        ArrayList<Integer> dp_sum = new ArrayList<>();

        for(int i = 0; i < n; i++)
        {
            int temp = sc.nextInt();
            arrayList.add(temp);
        }

        for(int i = 0; i < n; i++)
        {
            if(i == 0)
                dp_sum.add(arrayList.get(i));
            else if(i == 1)
                dp_sum.add(Math.max(arrayList.get(i - 1), arrayList.get(i)));
            else
            {
                int result = Math.max(dp_sum.get(i - 1), dp_sum.get(i - 2) + arrayList.get(i));
                dp_sum.add(result);
            }
        }
        System.out.println(dp_sum.get(n - 1));
    }

}

📝 정리

처음에는 해당 문제를 단순히 주어진 테스트 케이스만 보고 짝수와 홀수 값을 합쳐 계산한 값을 불러왔으나 생각해보니
아래와 같은 케이스에서 원하는 값을 못 불러온다.
7
1 3 1 5 1 1 9

겉보기로 계산할 시에 딱봐도 9 + 5 + 3 = 17이 가장 최고의 수이나
짝수/ 홀수 계산 시에 원하는 값을 못 불러온다.

이를 고려하여 로직을 짤 시 바텀업을 이용하여
a(i)는 해당 순차 시 최대로 털 수 있는 값이라고 하면
a(i) = max( a(i-1) , a(i-2) + 현재 창고 내 물자 값(k))의 점화식을 세워 풀 수 있다.