백준_21758_꿀 따기

꿀 따기

문제

아래와 같이 좌우로 N개의 장소가 있다.

장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.

두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.

1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

위의 그림과 같이 배치된 경우 두 마리의 벌 모두 $4 + 1 + 4 + 9 + 9 = 27$의 꿀을 따서, 전체 꿀의 양은 54가 된다.

위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 $9 + 4 + 4 + 9 + 9 = 35$의 꿀을 따고 오른쪽 장소에서 출발한 벌은 $4 + 9 + 9 = 22$의 꿀을 따므로, 전체 꿀의 양은
$57$이 된다.

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.

장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 장소의 수 $N$이 주어진다.

다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.

출력

첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.

제한

• $3 \le N \le 100~000$ 
• 각 장소의 꿀의 양은 $1$ 이상 $10~000$ 이하의 정수이다.

예제 입력 1

7
9 9 4 1 4 9 9

예제 출력 1

57

풀이 및 해설

출력값: 벌통과 벌 두 마리를 적절한 위치에 배치하여 벌들이 딸 수 있는 최대의 꿀의 양

벌통 1개와 벌 2마리를 일렬로 된 위치에 배치하는 경우
1) 벌통 위치가 가장 왼쪽에 있을 때

• 벌 한 마리는 가장 오른쪽에 위치
• 다른 한 마리는 벌통과 지정된 벌 사이의 최대 꿀을 딸 수 있는 위치 계산

2) 벌통 위치가 가장 오른쪽에 있을 때

• 벌 한마리는 가장 왼쪽에 위치
• 1)과 동일

3) 벌통 위치가 중간에 있을 때

• 두 벌이 양 끝에 존재

누적합 이용: 매번 꿀의 양 구하는 것이 아닌 누적합 이용해서 계산

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0]; // 장소의 수 N
const honey = input[1].split(' ').map(Number); // 각 장소에서 꿀을 딸 수 있는 양

const sum = Array.from({ length: N }, () => 0); // 누적합
sum[0] = honey[0];
for (let h = 1; h < N; h++) sum[h] = sum[h - 1] + honey[h];

let answer = 0;
// 1. 벌통 위치가 가장 왼쪽에 있을 때
// - 벌 한 마리는 가장 오른쪽에 위치
// - 다른 한 마리는 벌통과 지정된 벌 사이의 최대 꿀을 딸 수 있는 위치 계산
for (let i = 1; i < N - 1; i++)
  answer = Math.max(answer, sum[N - 2] + sum[i - 1] - honey[i]);

// 2) 벌통 위치가 가장 오른쪽에 있을 때
// - 벌 한마리는 가장 왼쪽에 위치
// - 1)과 동일
for (let i = 1; i < N - 1; i++)
  answer = Math.max(
    answer,
    sum[N - 1] - honey[0] - honey[i] + sum[N - 1] - sum[i]
  );

// 3) 벌통 위치가 중간에 있을 때
// - 두 벌이 양 끝에 존재
for (let i = 1; i < N - 1; i++)
  answer = Math.max(answer, sum[N - 2] - honey[0] + honey[i]);

console.log(answer);