DP - 개미 전사

문제

이것이 취업을 위한 코딩테스트다 with 파이썬 (https://youtu.be/5Lu34WIx2Us)

• 개미 전사가 부족한 식량을 충당하기 위해 식량 창고를 공격
• 각 식량 창고는 일직선상에 존재하며 각각 정해진 수의 식량을 저장하고 있다.
• 개미 전사는 서로 인접한 식량 창고를 공격할 수 없다.
  = 최소한 한 칸 이상 떨어진 식량 창고를 약탈 가능
• 식량 창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최대값을 구하는 프로그램을 작성하다.

 

입력 조건

• 첫째 줄에 식량창고 개수 N이 주어진다. (3 <= N <= 100)
• 둘째 줄에 공백을 기준으로 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0 <= K <= 1,000)

 

출력 조건

• 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최대값을 출력한다.

 

풀이

• 전체 식량 창고를 분할해서 계산
• 메모해 둘 작은 문제의 결과값은 'i번째 식량창고까지의 최적의 해'
• i번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최대값)
  1) i-1번째 식량창고까지의 최적의 해  (※i-1번째 창고와 i번째 창고는 서로 인접해 동시에 털 수 없음)
  2) i-2번째 식량창고까지의 최적의 해 + i번째 식량창고의 식량 개수
  두 가지 중 더 큰 경우를 고르면 된다.

 

코드

import java.util.Scanner;
import java.util.StringTokenizer;

// 개미 전사 문제
public class Main {
    // i번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최대값)
    public static int[] dp = new int[100];

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

        // 식량 창고 개수
        int n = sc.nextInt();

        // 식량 창고에 저장된 식량 개수
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            count[i] = sc.nextInt();
        }

        // 다이나믹 프로그래밍 진행 (Bottom-Up)
        dp[0] = count[0];
        dp[1] = Math.max(count[0], count[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + count[i]);
        }

        // 마지막 식량창고까지의 최적의 해 출력
        System.out.println(dp[n-1]);
    }
}