[이.코.테] Chapter 08 동적 프로그래밍 - 개미 전사 (java)

개미 전사 문제 (교재 220p)

난이도 ●●○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB

 

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을의 식량창고는 일직선으로 이어져있다. 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사는 최대한 많은 식량을 얻기를 원한다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

 

입출력 조건)

입력 조건	- 첫째 줄에 식량창고의 개수 N이 주어진다. (3 ≤ N ≤ 100)  - 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0 ≤ N ≤ 1,000)
출력 조건	첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

입출력 예시)

입력 예시	출력 예시
4 1 3 1 5	8

---

문제 풀이 방법

1. (i-1)번째 식량창고를 털기로 결정한 경우 현재(i)의 식량창고를 털 수 없다.
2. (i-2)번째 식량창고를 털기로 결정한 경우 현재(i)의 식량창고를 털 수 있다.

👉 따라서 1번과 2번 중 더 많은 식량을 털 수 있는 경우를 선택하면 된다.

 

이것을 점화식으로 표현하면 아래와 같다.

$a_{i}=max(a_{i-1},a_{i-2}+k_{i})$

$a_{i}$ : i번째에 얻을 수 있는 식량의 최댓값

 

소스 코드

package exam08_dynamic_programming;

import java.io.*;
import java.util.StringTokenizer;

public class Q2_AntSoldier {
    public static int solution(int[] k){
        int[] a = new int[k.length];

        a[0] = k[0];
        a[1] = Math.max(k[0], k[1]); 
        
        for (int i = 2; i < k.length; i++) {
            a[i] = Math.max(a[i - 1], a[i - 2] + k[i]);
        }

        return a[k.length-1];
    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine()); // 식량 창고의 개수
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] k = new int[n]; // 식량의 개수
        for (int i = 0; i < n; i++) {
            k[i] = Integer.parseInt(st.nextToken());
        }

        bw.write(solution(k)+"\n");

        br.close();
        bw.close();
    }
}