[Swift 알고리즘] 백준 21758 꿀 따기

안녕하세요 코코종입니다.

오늘은 5일차였습니다! 무려 골.드! (옛날에 풀어봤던거긴 한데 기억1도 안남)

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/06.
//

import Foundation
// 21758 꿀 따기 그리디 골5

// idea: 벌 벌 통 / 벌 통 벌 / 통 벌 벌 경우로 나눠보자?

let n = Int(readLine()!) ?? 0
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }

// case 1 벌 벌 통
// 통은 항상 맨끝에 있는게 유리(그래야 끝까지 가니까), bee1은 무조건 맨 왼쪽에 있어야 최대가 된다.
// b1 = arr[0]
// b2 = arr[i]
// 통 = arr[n-1]
var case1 = 0
for i in 1..<n-1 { // b2의 위치
    let b1 = arr[1...n-1].reduce(0, +) - arr[i]
    let b2 = arr[i+1...n-1].reduce(0, +)
    case1 = max(case1, b1 + b2)
}
//print(case1)

// case 2 벌 통 벌
// 벌은 무조건 양 끝에 있어야 최대가 된다(꿀이 1이상이라서)
// b1 = arr[0]
// b2 = arr[n-1]
// 통 = arr[i]
var case2 = 0
for i in 1..<n-1 { // 통의 위치
    let b1 = arr[1...i].reduce(0, +)
    let b2 = arr[i...n-2].reduce(0, +)
    case2 = max(case2, b1 + b2)
}
//print(case2)


// case 3 통 벌 벌
// 통은 무조건 맨 왼쪽, b2는 맨 오른쪽
// b1 = arr[i]
// b2 = arr[n-1]
// 통 = arr[0]
var case3 = 0
for i in 1..<n-1 {
    let b1 = arr[0..<i].reduce(0, +)
    let b2 = arr[0..<n-1].reduce(0, +) - arr[i]
    case3 = max(case3, b1 + b2)
}
//print(case3)

print(max(case1, case2, case3))

네.. 또 틀린거 가져와써요 ㅋㅋㅋㅋㅋㅋㅋㅋ

정확히는 55점짜리 풀이였습니다. (n이 10만까지인데 5000까지인가의 범위가 서브테스크로 55점이네요 ㅎ..) 그래도 혼자 고민해서 반 정도 맞았고 이후에 개선안을 바로 떠올렸어요!

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/07.
//

import Foundation
// 21758 꿀 따기 그리디 골5

// idea: 벌 벌 통 / 벌 통 벌 / 통 벌 벌 경우로 나눠보자?
// 55점인 이유 -> 10만에 가까운 경우에 지금 O(n^2) 이라서 reduce등을 할때마다 계산해줘야함.. -> 누적 합을 다른 배열로 만들자

let n = Int(readLine()!) ?? 0
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
var sumArr: [Int:Int] = [:]

var sum = 0
for i in 0..<arr.count {
    sum += arr[i]
    sumArr[i] = sum
}

// case 1 벌 벌 통
// 통은 항상 맨끝에 있는게 유리(그래야 끝까지 가니까), bee1은 무조건 맨 왼쪽에 있어야 최대가 된다.
// b1 = arr[0]
// b2 = arr[i]
// 통 = arr[n-1]
var case1 = 0
for i in 1..<n-1 { // b2의 위치
//    let b1 = arr[1...n-1].reduce(0, +) - arr[i]
    let b1 = sumArr[n-1]! - sumArr[0]! - arr[i]
//    let b2 = arr[i+1...n-1].reduce(0, +)
    let b2 = sumArr[n-1]! - sumArr[i]!
    case1 = max(case1, b1 + b2)
}
//print(case1)

// case 2 벌 통 벌
// 벌은 무조건 양 끝에 있어야 최대가 된다(꿀이 1이상이라서)
// b1 = arr[0]
// b2 = arr[n-1]
// 통 = arr[i]
var case2 = 0
for i in 1..<n-1 { // 통의 위치
//    let b1 = arr[1...i].reduce(0, +)
    let b1 = sumArr[i]! - sumArr[0]!
//    let b2 = arr[i...n-2].reduce(0, +)
    let b2 = sumArr[n-2]! - sumArr[i-1]!
    case2 = max(case2, b1 + b2)
}
//print(case2)


// case 3 통 벌 벌
// 통은 무조건 맨 왼쪽, b2는 맨 오른쪽
// b1 = arr[i]
// b2 = arr[n-1]
// 통 = arr[0]
var case3 = 0
for i in 1..<n-1 {
//    let b1 = arr[0..<i].reduce(0, +)
    let b1 = sumArr[i-1]!
//    let b2 = arr[0..<n-1].reduce(0, +) - arr[i]
    let b2 = sumArr[n-2]! - arr[i]
    case3 = max(case3, b1 + b2)
}
//print(case3)

print(max(case1, case2, case3))

 

아이디어는 맞았는데 매번 array의 sum을 해주는게 문제라면 그걸 반복해서 안하도록 하면 되잖아요? 그래서 누적합인 sumArray를 만들었답니다. (그마저도 append 안하려고 dictionary로 해서 사실 array는 아님)

첫 아이디어는 맞았으니까 한 번 보면서 참고해보세요!

그리디다 보니까 일단 끝에 다 보내버리기~~ ㅋㅋㅋ 조금만 생각해보면 여러분들도 아이디어를 얻으실 수 있을겁니다!