개미 전사

출처

언어

  • JavaScript

문제 풀이 step 1

  • 점화식
    • dp[N] = N 개의 식량창고 중에서 뺏을 수 있는 식량의 최댓값
  • 경우
    1. N 번째 식량창고를 터는 경우
    2. N 번째 식량창고를 털지 않는 경우

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
// const input = `4
// 1 3 1 5`.split("\n");

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input[1].split(" ").map(Number);
	const dp = [];
	dp[0] = arr[0];
	dp[1] = Math.max(arr[0], arr[1]);

	for (let i = 2; i < n; i++) {
		dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
	}

	return dp[n - 1];
};

console.log(solution(input));