문제

개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있ㄷ으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.

{1, 3, 1, 5}

이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량창고가 이렇게 일직선상일 때 최와

개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

입력

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

출력

• 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

풀이

두칸을 연속해서 선택하면 안 된다는 점에 유의하여 점화식을 생각해내야 한다. 개미전사가 얻을 식량의 최댓값을 구하는 문제이기 때문에

$dp[i]=max(dp[i-2]+arr[i], dp[i-1])$

와 같이 식을 세워야한다.

즉, i 위치의 식량을 먹을 경우 먹을 수 있는 가장 인접한 식량이 i-2이 되므로 i-2까지의 식량 최댓값(dp[i-2])와 현재 식량(arr[i])을 더하여 준다. 이 경우를 i 위치의 식량을 먹지 않고 i-1까지 먹었을 때의 식량 최댓값과 비교하여 더 큰 값을 dp[i]에 저장하여 준다.

이때 현재 위치에서 2칸 떨어진 위치의 값이 계산에 사용되기 때문에 dp[0]과 dp[1]은 메인함수에서 초기화 해준다. dp[0]은 가장 앞에 있는 식량밖에 먹을 것이 없기 때문에 arr[0]으로 초기화 해주고 dp[1]의 경우 arr[0]과 arr[1] 중 더 큰 값으로 초기화 해준다.

코드

package Ch8_dp;

import java.util.*;
import java.io.*;
public class 실전3_개미전사 {

	static int[] arr;
	static int[] dp;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		arr=new int[N];
		for(int i=0;i<N;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		dp=new int[N];
		dp[0]=arr[0];
		dp[1]=Math.max(arr[0], arr[1]);
		
		System.out.println(solution());
	}

	static int solution() {
		for(int i=2;i<dp.length;i++) {
			dp[i]=Math.max(dp[i-1], arr[i]+dp[i-2]);
		}
		
		return dp[dp.length-1];
	}
}