백준 21758 꿀 따기 Kotlin (그리디, 누적 합)

문제 출처 : https://www.acmicpc.net/problem/21758

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≤N≤100 000 
• 각 장소의 꿀의 양은 1 이상 10000 이하의 정수이다.

서브태스크

 

알고리즘 분류

• 그리디 알고리즘
• 누적 합
• 많은 조건 분기

풀이

그리디 + 누적 합 문제이다.

우선 N이 100000이기 때문에, 완전 탐색이 가능한지 봐야 한다.

보통 N이 이렇게 큰 경우, 완전 탐색으로는 풀 수 없는 경우가 많다. O(n^2)인 알고리즘만 돌려도 시간 초과이기 때문이다.

그러면, 어떻게 탐색 범위를 줄일 수 있는지 찾는 것, 시간 복잡도가 작은 알고리즘을 사용하는 것이 관건이다.

우선 꿀통의 위치에 따른 경우들을 확인해 보자.

꿀통이 맨 왼쪽에 있다면, 벌 한 마리는 가장 우측에 있는 것이 유리하다.

나머지 한 마리 벌은 어느 위치가 유리한지 단정 지을 수 없다.

고로, 현재 최선은 벌 한 마리는 가장 우측에, 나머지 벌은 맨 왼쪽과 맨 우측을 제외한 가운데 범위에서 최댓값이 되는 경우를 찾는 것이 최선이다.

 

꿀통이 맨 오른쪽에 있어도 위와 같다.

 

꿀통이 맨 왼쪽이나, 맨 오른쪽이 아닌 가운데 범위에 있다고 생각하면, 어떠한 경우에도 두 마리의 벌은 양쪽 끝,

즉, 맨 왼쪽, 맨 오른쪽에 있어야 유리하다.

 

정리하면,

1. 꿀통이 맨 왼쪽, 맨 오른쪽에 있을 땐, 벌 한 마리는 맨 왼쪽, 맨 오른쪽에 있고, 한 마리는 그 사이 어딘가에 있다.

2. 꿀통이 1~n-1사이에 있다면 두 벌은 맨 왼쪽, 맨 오른쪽에 있다.

 

탐색 범위가 훨씬 줄었다. 이는, 항상 최적의 해를 찾는 그리디(탐욕법)이라 할 수 있다.

 

벌이 꿀을 따는 로직은, 배열을 순회해야 하기 때문에, 최댓값을 찾는 과정에서 같은 동작을 반복하게 된다.

따라서 이 반복을 줄이기 위해, 미리 왼쪽-> 오른쪽, 오른쪽-> 왼쪽 으로 벌이 꿀을 따는 합을 미리 구해놓고,

이후 최댓값을 찾는 과정에서 미리 구한 누적 합을 이용하면 된다.

만약 벌이 2에 있고 꿀통이 6에 있다면,

leftSum[6]-leftSum[2]이 될 것이다. // 3,4,5,6의 꿀을 딴 값

 

벌의 위치한 곳은 꿀을 따지 못하는 것에 유의하자.

 

 

코드

import kotlin.math.*
fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val arr = br.readLine().split(' ').map{it.toLong()}
    val leftSum = LongArray(n)
    val rightSum = LongArray(n)
    leftSum[0] = arr[0]
    rightSum[n-1] = arr[n-1]
    for(i in 1 until n){
        leftSum[i] += leftSum[i-1]+arr[i]
        rightSum[n-i-1] +=rightSum[n-i]+arr[n-i-1]
    }
    rightSum[0] = rightSum[1]+arr[0]

    var answer=0L
    val left = leftSum[n-2]-arr[0]
    val right = rightSum[0]-arr[n-1]
    for(i in 1 until n-1){
        //벌통이 우측인 경우
        answer = max(answer,left + (leftSum[n-1]-leftSum[i])-arr[i]+arr[n-1])
        //벌통이 좌쪽인 경우
        answer = max(answer, right + (rightSum[1]-rightSum[i])-arr[i] +arr[0])
        //벌통이 가운데(1~n-2)인 경우
        answer = max(answer, leftSum[i]+rightSum[i]-arr[0]-arr[n-1])
    }

    write("$answer")
    close()
}