백준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

예제 입력 2

7
4 4 9 1 9 4 4

예제 출력 2

54

예제 입력 3

3
2 5 4

예제 출력 3

10

문제 해결 과정

문제 해결 방법이 생각나지 않아 30분 동안 노트에 끄적인 후, 바로 블로그를 참고했다.
일단 세 가지 케이스가 존재한다.
1. 벌 - 벌 - 꿀통
2. 꿀통 - 벌 - 벌
3. 벌 - 꿀통 - 벌

1번의 경우는 왼쪽 벌과 꿀통이 각 끝에 위치한다.
2번의 경우는 꿀통과 벌이 각 끝에, 3번의 경우는 각 벌이 각 끝에 위치한다.

이렇게 각 케이스마다 for 문을 돌린 후, 가장 큰 값을 출력해야한다.

일단 먼저 꿀의 양이 담긴 배열을 for 문을 돌리며, 0번째 부터 i번째의 합을 sum이라는 배열에 넣는다.

1번의 경우는 벌과 꿀통이 고정이기 때문에 벌의 위치(i)에 따라 값을 더해서 최댓값을 찾으면 된다.
벌 위치가 있는 곳의 꿀의 양은 계산하지 않기 때문에 인덱스 1번째~인덱스 N-1까지 합을 구하고 벌의 위치 i의 꿀의 양을 뺀다. 그리고 i+1 부터 N-1까지의 합을 구한다.

2번의 경우는 왼쪽 꿀통과 오른쪽 벌이 고정이기 때문에 가운데 벌의 위치에 따라 구하면 된다.
이번에는 0번째부터 i-1까지의 합과 0번째 부터 N-2까지의 합에서 i의 꿀의 양을 빼면 된다.

3번의 경우는 꿀통의 위치에 따라 달라진다.
1번째 부터 i까지 구하고, i부터 N-2까지 더해서 구한다.

최종 코드 (Python)

N = int(input())

honey = list(map(int,input().split()))

result = 0

sum = []
sum.append(honey[0])

for i in range(1, N) :
    sum.append(sum[i-1]+honey[i])

# case 1 벌통 - 벌 - 벌

for i in range(1, N-1) :
    result = max(result, sum[N-2] + sum[i-1] - honey[i])

# case 2 벌 - 벌 - 벌통
for i in range(1, N-1) : 
    result = max(result, sum[N-1] - sum[i] + sum[N-1]-honey[i]-honey[0])

# case 3 벌 - 벌통 - 벌
for i in range(1, N-1) :
    result = max(result, sum[N-2] - honey[0] + honey[i])

print(result)

최종 코드 (JavaScript)

const fs = require('fs');

// 입력 파일 경로 설정 (백준 등에서 입력받을 때 '/dev/stdin' 사용)
// 로컬 테스트할 경우 'input.txt'를 사용할 수도 있음
const readFileSyncAddress = '/dev/stdin';
// const readFileSyncAddress = 'input.txt';

// 입력을 읽어와 줄 단위로 나눈 후, 배열로 변환
const input = fs
  .readFileSync(readFileSyncAddress)
  .toString()
  .trim()
  .split("\n");

function solution(input){
    let N = input[0]
    let honey = input[1].toString().trim().split(' ').map(Number)

    let result = Number(0)
    let sum = []
    sum.push(honey[0])

    for (let i = 1; i<=N-1; i++){
        sum.push(sum[i-1]+honey[i])
    }
    // case 1, 벌 - 벌 - 벌통
    for (let i = 1; i<N-1; i++){
        if (result < sum[N-1] - honey[i] - honey[0] + sum[N-1] - sum[i]){
            result = sum[N-1] - honey[i] - honey[0] + sum[N-1] - sum[i]
        }
    }

    // case 2, 벌통 - 벌 - 벌
    for (let i = 1; i<N-1; i++){
        if (result < sum[i-1] + sum[N-2] - honey[i]){
            result = sum[i-1] + sum[N-2] - honey[i]
        }
    }

    // case 3, 벌 - 벌통 - 벌
    for (let i = 1; i<N-1; i++){
        if (result < sum[i] - honey[0] + sum[N-2]- sum[i-1]){
            result = sum[i] - honey[0] + sum[N-2]- sum[i-1]
        }
    }

    console.log(result)

}

solution(input)

새로 알게 된 점

JavaScript

Math.max() -> 매개변수로 주어진 숫자 중 가장 큰 수를 반환하거나, 매개변수가 없을 경우 Infinity를 반환