[백준] 21758 꿀 따기 - javascript

📌 문제

https://www.acmicpc.net/problem/21758

📌 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const n = +input.shift();
const arr = input.shift().split(' ').map(Number);
const sum = new Array(n + 1).fill(0);
let ans = 0;

arr.unshift(0);

for (let i = 1; i <= n; i++) {
  sum[i] = arr[i] + sum[i - 1];
}

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

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

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

✔ 알고리즘 : 그리디

✔ 가능한 경우의 수는 총 3가지이다

• 꿀통 ~ 벌 ~ 벌
  이 경우 꿀통은 맨 왼쪽, 두번째 벌은 맨 오른쪽에 배치를 해야 최대의 꿀을 딸 수 있다. 따라서 첫번째 벌을 움직이면서 ans를 갱신해주면 된다.

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

• 벌 ~ 꿀통 ~ 벌
  이 경우 벌은 양끝에 위치해야 최대의 꿀을 딸 수 있다. 따라서 꿀통을 움직이면서 ans를 갱신해주면 된다.

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

• 벌 ~ 벌 ~ 꿀통
  이 경우 꿀통은 맨 오른쪽, 첫번째 벌은 맨 왼쪽에 배치해야 최대의 꿀을 딸 수 있다. 따라서 두번째 벌을 움직이면서 ans를 갱신해주면 된다.

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

✔ 난이도 : 백준 기준 실버 1