그리디는 직관적으로 문제를 이해해야 해서 너무 어려운것 같다..
3가지의 경우가 있다.
그전에 먼저 조건
- 왼쪽에 있는 벌을 b1
- 오른쪽에 있는 벌을 b2
- 벌통을 pivot
위와 같이 정의하고
두번째 벌통부터 끝에서 두번째 벌통까지 순회한다.
각 방문하는 벌통에 대해서
- 해당 벌통이
pivot즉 b1 -> pviot <- b2 와 같은 상황 - 해당 벌통이 b2 이때 b1은 자연스럽게 맨 왼쪽 벌통, pivot은 맨 오른쪽 벌통 b1 -> b2 -> pivot
- 해당 벌통이 b1 이때 b2는 자연스럽게 맨 오른쪽 벌통, pivote은 맨 왼쪽 벌통 pivot <- b1 <- b2
import Foundation
let n = Int(readLine()!)!
let baskets: [Int] = [0] + readLine()!.split(separator: " ").map { Int(String($0))! }
var sums: [Int] = baskets
var answer = 0
(1...n).forEach { sums[$0] += sums[$0 - 1] }
func beeSum(l: Int, r: Int) -> Int {
return sums[r] - sums[l-1]
}
(2..<n).forEach { i in
answer = max(answer, beeSum(l: 2, r: i) + beeSum(l: i, r: n-1)) // --> p <--
answer = max(answer, beeSum(l: 2, r: n) + beeSum(l: i+1, r: n) - baskets[i]) // --> --> p
answer = max(answer, beeSum(l: 1, r: n-1) + beeSum(l: 1, r: i-1) - baskets[i]) // p <-- <--
}
print(answer)