[이코테] 개미 전사, DP

문제 풀이

보통 이런 문제 처럼 처음부터 끝가지 참조하며 현재 참조하고 있는 부분을 포함해야 할지 말아야 할지 결정해서 원하는 조건을 충족하려면 이전 값들을 알아야 한다. 하지만 그 길이가 길면 길 수록 이전 값들을 계속 계산해야 한다. 따라서 성능상 이전 값들의 연산 결과를 저장하여 보관해두면 바로 꺼내 쓸 수 있어 효율적이다.
이 문제도 마찬가지이다.

0과 1번 인덱스에 한해서는 바로 값을 지정해두고 반복문을 통해

max(이전 값, 2번째 전 값+현재 값)을 통해 더 큰 값을 택한다

위 로직을 코드로 작성해보자.

코드

package 이코테.기출분석.DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

import static java.lang.Math.*;

public class 개미전사 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] storage = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

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