다이나믹 프로그래밍 - 개미전사

문제

---

 

 

 

문제해결

---

f(i)는 i번째 식량창고까지 얻을수있는 식량의 최대값이고

k(i)는 i번째 식량창고에 있는 식량의 양일때

f(i) = max(f(i-1), f(i-2) + k(i))

f(i-1) : i번째 식량창고를 약탈하지 않을때

f(i-2) + k(i) : i번째 식량창고를 약탈할때

둘중 더 큰 값을 dp 배열에 저장

import java.util.Scanner;

public class Ex02개미전사 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        //앞서 계산된 결과를 저장하는 dp 테이블
        int[] dp = new int[n];

        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + arr[i]);
        }
        System.out.println(dp[n-1]);
    }
}