[이코테_JAVA] DP문제 풀이_개미전사 [투 포인터 풀이 + DP 풀이]

잘못된 접근.

처음 이 문제를 받아 들였을 때는 잘못된 접근을 했다.
인접하지 않은 최댓값을 가지고 오면 된다고 해서,
단순하게 떨어진 두 개의 값을 더하는 형태로 최대 최소를 나눈다고 생각한 것이다.

그에 아래와 같은 잘못된 코드를 생산한 예이다.

public class 실전문제2_개미전사 {
    private static void solution(int N, int[] foods) {
        int evenMax = 0;
        int oddMax = 0;
        for(int i = 0; i < N; i += 2){
            evenMax += foods[i];
        }
        for(int i = 1; i < N; i += 2){
            oddMax += foods[i];
        }
        System.out.println(Math.max(evenMax,oddMax));
    }

    public static void main(String[] args) {
        solution(4, new int[] {1,3,1,5});
    }
}

투포인터를 활용한 접근(시간 복잡도O(N^2))

위의 잘못된 접근을 확장해 보는 건 어떨까?
투포인터를 활용해 가장 큰 값을 만들 수 있는 방법도 존재해서 구현해 보았다.
하지만 위에 설명한 것처럼 이 경우 시간 복잡도가 O(N^2)이다.
즉 값이 기하급수적으로 많은 배열이라면 이 방법은 좋은 방법이 아니다.
연산량이 기하급수적으로 늘기 때문이다.

public class 실전문제2_개미전사 {

    private static void solution2(int N, int[] foods){
        int[] dp = new int[2];
        int p1 = 0;
        int p2 = 1;
        int p3 = foods.length-1;//mover
        while(p1 + 1 < p3){//인접하지 않도록 만드는 값.
            int sum = 0;
            for(int i = p1; i <= p3; i+=2){
                sum += foods[i];
            }
            dp[0] = Math.max(sum, dp[0]);
            p3--;
        }
        p3 = foods.length -1;
        while(p2 + 1 < p3){
            int sum = 0;
            for(int i = p2; i <= p3; i+=2){
                sum += foods[i];
            }
            dp[1] = Math.max(sum, dp[1]);
            p3--;
        }
        System.out.println(Math.max(dp[0],dp[1]));
    }
    public static void main(String[] args) {
        solution2(8, new int[] {1,3,5,5, 100, 200, 300000000, 50000});
    }
}

이제 드디어 dp를 활용해 보자. 시간복잡도 O(N)

그냥 손 쉽게 dp 문제니까 dp로 풀면 되지! 이렇게 접근하는 것도 좋지만
나 같은 경우에는 아직 dp가 익숙하지 않았다.
그래서 dp를 떠올리기도 쉽지 않았다.
어떤 말이냐면, 어떻게 해야, 이 dp의 사이즈를 결정할 수 있지?

이 부분부터가 난제였다.

그래서 위와 같은 삽질들을 했다.
종합적으로 검증해 봤을 때, 아래의 코드는
시간복잡도 측면에서 O(N)만을 가진다.

즉, 가장 빠르게 문제를 풀 수 있는 방법 중 하나인 것이다.

또한 코드도 깔끔하다.
제한 조건을 보면 N은 3을 최소의 크기로 가진다는 부분 역시 해당 요소를 손쉽게 구현할 수 있는 여지를 만들어 준다.

필자는 점화식을 An = Math.max(An-1,An-2 + kn)으로 알려주고 있다.

이 말은 해당하는 위치 값을 갱신할 때, 이전의 값이 더 큰지 또는 인접하지 않은 값과 현재의 foods 배열에 들어 있는 값의 합 둘 중에 큰 값을 골라 담으라는 이야기다.

이렇게 되면, 가장 큰 값만 An에는 담기고 이를 활용하면, dp의 배열은 foods의 길이보다 +1인 상태로 만들 수 있고(같게 만들어도 되긴 한다.)

이를 통해 구하고자 하는 최대값을 dp[N]에 담는 식을 구현할 수 있다.

실제 수학에서는 최대값이라는 여부의 점화식이 존재하지 않지만,
컴퓨터를 활용한 연산에서는 이러한 점화식도 세울 수 있다는 점이 나름의 팁으로 다가왔고, 이 문제 역시 타뷸레이션(tabulation)(bottom-up) 방식으로 재귀가 아닌 for를 이용한 메모리 효율성을 높였다.

public class 실전문제2_개미전사 {
    private static void solution3(int N, int[] foods){
        int[] dp = new int[foods.length+1];
        dp[1] = foods[0];
        dp[2] = foods[1];
        //최소 N은 3;
        for(int i = 3; i <= N; i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+foods[i-1]);
        }
       System.out.println(dp[N]);
    }
    public static void main(String[] args) {
        solution3(8, new int[] {1, 1, 100, 101, 100, 100, 50000, 1000000});
    }
}