백준 21758 꿀 따기

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

꿀이 있는 장소들이 주어지며, 이중에 한 곳을 골라 벌통으로, 두 곳을 골라 벌의 위치로 (모두 서로 다름) 정한다.

두 벌은 벌통 쪽으로 직선으로 이동하며 꿀을 모으는데, 벌이 있던 위치에선 꿀을 모을 수 없다.

꿀을 최대로 모을 수 있는 벌 두마리와 벌통의 위치를 고르는 문제이다.

일단, 장소의 개수는 최대 100,000개 이고 각 장소의 꿀의 양은 최대 10,000이므로 Int 범위를 넘어갈 가능성이 있다는 것을 파악했다.

접근 방법을 생각할 때, 나는 벌통의 위치를 기준으로 생각해 보았다.

1. 벌통이 한 쪽 끝에 위치하는 경우.
   왼쪽 끝이나 오른쪽 끝인 경우, 구하는 방법은 유사하므로 오른쪽 끝이라고 생각해보자.

벌통이 오른쪽 끝인 경우, 벌 한 마리는 반드시 왼쪽 끝이어야 한다고 생각했다.
왼쪽 끝에 놓으면 첫 번째 장소의 꿀만 얻지 못하고 시작하지만, 그 외에 위치라면 버리는 장소가 많아지기 때문이다.

따라서 벌 한마리를 왼쪽 끝에 놓은 뒤, 나머지 한 마리의 벌을 인덱스 1부터 벌통의 위치까지 옮겨 보며 꿀의 합을 구해보면 된다. (효율을 위해 부분합 사용)

2. 벌통이 끝에 위치하지 않는 경우.
   일반적으로는 1번처럼 한쪽 끝에 통을, 한쪽 끝에 벌을 놓는 방식이 맞다.

하지만 1 10 1, 2 5 3 등 양쪽 끝에 벌을 놓고 가운데 통을 놓아야 최대의 꿀을 얻는 경우가 있다.

이 케이스에서 중요한 것은 꿀이 가장 많은 장소의 인덱스이다.
만약 꿀이 가장 많은 장소가 양쪽 끝이 아닌 위치라면, 양쪽 끝에 벌을 놓고 꿀이 가장 많은 장소에 벌통을 두어서 가장 많은 꿀 * 2를 얻을 수 있도록 해 본다.

간단한 예시로 풀이과정을 따라가 보자.

예시 케이스는 1 1 10 1이다.

1. 오른쪽 끝에 벌통을 놓는 경우.
   벌통 위치부터 왼쪽 방향으로 부분합을 구한다 (13 12 11 1)
   왼쪽 끝에 벌이 있다 가정하고, 1번 위치부터 벌통 전 위치까지 꿀을 구해본다.
   0번, 1번 위치에 벌을 놓는 경우 > 13 + 12 - 1 - 1 2 = 22
   0번, 2번 위치에 벌을 놓는 경우 > 13 + 11 - 1 - 10 2 = 3
   (두 벌 위치 부분합 값 - 첫 번째 벌 장소 꿀 - 두 번째 벌 장소 꿀 * 2)

2. 왼쪽 끝에 벌통을 놓는 경우.
   벌통 위치부터 오른쪽 방향으로 부분합을 구한다 (1 2 12 13)
   오른쪽 끝에 벌이 있다 가정하고, 2번 위치부터 1번 위치까지 꿀을 구해본다.
   2번, 3번 위치에 벌을 놓는 경우 > 12 + 13 - 1 - 10 2 = 4
   1번, 3번 위치에 벌을 놓는 경우 > 2 + 13 - 1 - 1 2 = 12

3. 꿀이 가장 많은 장소에 벌통을 놓는 경우 (양쪽 끝 아닐 경우만)
   2번 위치에 벌통을 놓고 양쪽 끝에 벌이 있다 가정한 뒤 합을 구한다.
   1 + 10 + 10 = 21

따라서 가장 최댓값을 오른쪽 끝에 벌통을 두고 0번 1번 위치에 벌을 놓아 22를 얻는 경우이다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()

    val honey = readLine().split(' ').map{it.toLong()}
    var sum = LongArray(N){0}

    var maxHoney = 0L
    var maxIdx = 0
    for(i in honey.indices){
        if(i == 0) sum[i] = honey[i]
        else sum[i] = sum[i - 1] + honey[i]
        if(maxHoney < honey[i]){
            maxHoney = honey[i]
            maxIdx = i
        }
    }
    var max = 0L

    // 왼쪽 끝 통
    for(i in sum.size - 2 downTo 1){
        val s = sum[N - 1] + sum[i] - honey[N - 1] - 2 * honey[i]

        if(max < s) max = s
    }

    // 오른쪽 끝 통
    for(i in honey.indices.reversed()){
        if(i == honey.size - 1) sum[i] = honey[i]
        else sum[i] = sum[i + 1] + honey[i]
    }

    for(i in 1 until sum.size - 1){
        val s = sum[0] + sum[i] - honey[0] - 2 * honey[i]

        if(max < s) max = s
    }

    var case3 = 0L
    // 맥스값 통
    if(maxIdx != 0 && maxIdx != N - 1) {
        for (i in 1..maxIdx) {
            case3 += honey[i]
        }
        for (i in honey.size - 2 downTo maxIdx) {
            case3 += honey[i]
        }
        if (case3 > max) max = case3
    }

    print(max)
}