개미 전사 - '이것이 코딩 테스트다 with 파이썬'

이것이 취업을 위한 코딩 테스트다 with 파이썬

'개미 전사' 문제에 대해서 풀어 보겠습니다. 1차원으로 나열된 메뚜기 창고 에서 각 식량의 갯수가 주어졌을 때, 최소 한칸 이상 떨어져 있어야 식량 창고를 털 수 있습니다. 이 털 수 있는 최대 식량의 갯수를 출력 하는 문제 입니다. 

 

 

1. 접근

1. 짝수인 창고 칸만 털 경우

2. 홀수인 창고 칸만 털 경우

3. 두 경우 중 더 큰 경우 출력

처음에는 위와 같이 접근 했다. 하지만, 창고가 2칸 떨어져서 털 경우와 임의로 더 큰 경우가 있을수 있습니다.

 

public class Page220 {
    //식량 창고
    // N (3 <= N <= 100)
    // K (0 <= K <= 1000)
    //입력 예시
    // 4
    // 1 3 1 5
    //출력 예시
    // 8
    public static void main(String[] args) {
        int N = 4;
        int[] array = {1, 3, 1, 5};
        System.out.print(new Page220().solution(N, array));
    }

    int solution(int N, int[] array){
        //1. 짝수 열씩의 총합
        //2. 홀수 열씩의 총합
        // 둘 총합 중의 더 큰 값 출력
        int evenSum = 0;
        int oddSum = 0;

        for (int i = 0; i < N; i++) {
            // 짝수 인 경우
            if(i % 2 == 0)
                evenSum = evenSum + array[i];
            // 홀수 인 경우
            if(i % 2 == 1)
                oddSum = oddSum + array[i];
        }

        if(evenSum < oddSum)
            return oddSum;
        else
            return evenSum;
    }
}

 

따라서 이렇게 구현 하면 제대로 된 출력 결과를 얻을 수 없습니다. 이 전의 구한 최대값을 기억하고, 다음 상황에서 처한 dp[i-1]의 경우와 dp[i-2] + array[i]를 비교 하여 더 큰 값으로 d[i]를 업데이트 하는 접근으로 해결 할 수 있습니다. 따라서, dp[i] = Math.max(dp[i-1] , dp[i-2] + array[i]) 이와 같은 점화식을 세우고, 다이나믹 프로그래밍(DP) 접근 방식으로 구현 하였습니다.

 

public class Page220_2 {
    //식량 창고
    // N (3 <= N <= 100)
    // K (0 <= K <= 1000)
    //입력 예시
    // 4
    // 1 3 1 5
    //출력 예시
    // 8
    public static void main(String[] args) {
        int N = 4;
        int[] array = {1, 3, 1, 5};
        System.out.print(new Page220_2().solution(N, array));
    }

    int solution(int N, int[] array){
        //1. 짝수 열씩의 총합
        //2. 홀수 열씩의 총합
        // 둘 총합 중의 더 큰 값 출력
        // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
        int[] dp = new int[100];

        // 다이나믹 프로그래밍(DP 보텀업)
        dp[0] = array[0];
        dp[1] = Math.max(array[0], array[1]);
        for (int i = 2; i < N; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + array[i]);
        }
        return dp[N - 1];
    }
}