개미 전사

 

첫번째와 두번째 식량창고를 털때를 알 수가 있다.

그러면 어떻게 보텀업 방식으로 올라갈 수 있을까 생각해보자

d[0] = 3 d[1] = 1 or 3 중 큰 값으로 둔다.

d[2]는 어떻게되냐면 d[0] + arr[2] 하거나 d[1]만 선택하는게 최댓값이 된다. d[2] = d[0] + arr[2] 가 됐다.

d[3]은 d[1] + arr[3] 하거나 d[2]만 선택하는게 최댓값이 된다. 

여기서 d[0]은 고려 안해도 되는 이유는 이미 d[2]에서 선택된 최댓값이 들어가 있기 때문이다.

 

점화식을 세우면 단순히 d[i] = Math.max(d[i-2]+arr[i], d[i-1]); 이 된다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = kb.nextInt();

        //약탈한 식량을 저장하기위한 dp 테이블
        int[] dp = new int[n];

        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        //3번째부터는
        //현재식량을 털어서 2칸 전에 있는 식량을 털거나
        //현재식량을 털지 않아서 1칸전에 있는 식량을 터는 방법을 선택한다.
        for(int i = 2; i < n ; i++) {
            dp[i] = Math.max(dp[i-2] + arr[i], dp[i-1]);
        }
        System.out.println(dp[n-1]);


    }
}