[코딩 테스트] 🚚 택배 배달과 수거하기 - 2023 KAKAO BLIND

Greedy를 활용한 문제

가장 먼 거리까지 왕복을 몇번 해야 하는가인지 깨달아야 하는 문제

풀이 과정

• 총 이동 거리는 결국 가장 먼 집까지 몇 번 왕복했는지에 의해 결정된다.
• 따라서 가장 먼 집부터 거꾸로 살펴보며, 그 지점까지 배달/수거가 남아 있다면 왕복을 추가해야 한다.
• 왕복 1회에서 배달 최대 cap, 수거 최대 cap을 동시에 처리할 수 있다.

소요시간

• 1시간 이상
• GPT 도움 받음

import Foundation

func solution(_ cap:Int, _ n:Int, _ deliveries:[Int], _ pickups:[Int]) -> Int64 {
    var ans: Int64 = 0      // 총 이동 거리
    var d = 0               // 현재 인덱스까지 남은 배달량(누적)
    var p = 0               // 현재 인덱스까지 남은 수거량(누적)

    // 집 n-1 → 0 (가장 먼 집부터 역순으로 처리)
    for i in stride(from: n-1, through: 0, by: -1) {
        d += deliveries[i]  // i번째 집까지 필요한 배달 누적
        p += pickups[i]     // i번째 집까지 필요한 수거 누적

        // 이 위치까지 배달/수거가 남아 있으면 왕복 필요
        while d > 0 || p > 0 {
            // 한 번 왕복: 트럭 적재량(cap)만큼 배달/수거 처리
            d -= cap
            p -= cap
            // 왕복 거리 추가 (i+1은 실제 거리, *2는 왕복)
            ans += Int64((i + 1) * 2)
        }
    }

    return ans
}

회고

그리디 알고리즘 복습이 필요함