[이것이 취업을 위한 코딩테스트다] Ch08. 다이나믹 프로그래밍 - 개미 전사 (Java)

문제

개미 전사가 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다

메뚜기 마을에는 여러 개의 식량창고가 있는데 일직선으로 이어져 있다.

각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 

메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량차고가 공격받으면 바로 알아챌 수 있다.

따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.

개미 전사는 식량창고가 일직선상일 때 최대한 많은 식량을 얻기를 원한다.

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

 

(예시입력)

4

1 3 1 5

(예시출력)

8

 

풀이/후기

(바로 앞 까지의 최적의 해)와 (두칸 앞 까지의 최적의 해 + 현재 위치의 해)를 비교해 더 높은 값을 d[]에 저장함

*이미 반복문을 통해 앞 칸(i-3)까지의 최적의 해는 구해졌기 때문에, 구하고자 하는 칸을 볼 때는 한 칸 앞과 두 칸 앞을 고려하면 됨!

코드

package ThisIsCT;

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

public class ch08_03 {
	// Ch.08 다이나믹 프로그래밍 Dynamic Programming DP
	// 개미 전사
	// 유튜브 풀이 영상 : https://www.youtube.com/watch?v=5Lu34WIx2Us

	static int[] d = new int[100 + 1];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		for (int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(str.nextToken());
		}
		
		/*
		 * (바로 앞까지의 최적의 해)와
		 * (두칸 앞까지의 최적의 해 + 현재 위치의 해)를 비교하여 더 높은 값을 d[]에 저장함
		 */
		
		
		//0과 1번째는 항상 아래와 같고, 반복문은 2부터(세번째) 돌려줌
		d[0] = arr[0];
		d[1] = Math.max(arr[1], arr[0]);
		for (int i=2; i<N; i++) {
			d[i] = Math.max(d[i-1], d[i-2] + arr[i]);
		}
		
		System.out.println(d[N-1]);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/4cf375d58b476bb8ab3c28208cf4c53fedc8d712

참고

이코테 유튜브 - 다이나믹 프로그래밍 참고

https://www.youtube.com/watch?v=5Lu34WIx2Us