백준 8980 택배

출처: www.acmicpc.net/problem/8980

분류: 그리디

---

접근방식

출발 도시와 도착 도시, 용량이 적혀있는 택배 목록이 주어질 때 배달할 수 있는 최대 용량을 구하는 문제입니다.
단, 한번 지나온 마을은 다시 돌아갈 수 없습니다.

핵심 포인트는 다음 2가지 입니다.

문제의 핵심은 도착 도시를 기준으로 정렬
각 도시에서 적재 가능한 용량 체크

특히 도착 도시를 기준으로 정렬하는 것이 핵심인데요,
도착 도시를 기준으로 정렬했기 때문에 가장 먼저 내릴 수 있는 택배를 우선적으로 배달할 수 있습니다.

예를 들어,

3 60
3
1 3 50
1 2 30
2 3 60

이렇게 주어질 때 도착 기준으로 정렬합니다.

1 2 30
1 3 50
2 3 60

가장 먼저 도착하는 2번 마을에 배달해야 할 양 30을 최대한으로 실어줍니다. 
그리고 각 마을에서 택배에 적재되어 있는 양을 살펴보면,

30 0 0

아직 택배 용량 30만큼을 더 실을 수 있기 때문에, 
3번 마을까지 배달하는 50에서 30만큼을 더 실어줍니다.

60 30 0

다음으로 2번 마을에 가서 역시 나머지 30만큼을 더 실어줄 수 있습니다.

60 60 0

 

같은 방법으로 다음 같은 케이스도 해볼까요?

6 60
5
1 2 30
2 5 70
5 6 60
3 4 40
1 6 40

정렬부터 하면,
1 2 30
3 4 40
2 5 70
1 6 40
5 6 60

각 도시에서 적재 용량을 살펴보면,
30 0 0 0 0 0  ==> 총 배달한 양: 30
30 0 40 0 0 0 ==> 70
30 20 60 20 0 0 ==> 90
30 20 60 20 0 0 ==> 90
30 20 60 20 60 0 ==> 150

1번 마을에서 1 6 40 을 실어버리면 5번마을 까지는 계속 들고있어야 하기 때문에 배달할 수 있는 다른 물건들을 배달해줄 수가 없게 됩니다.
따라서 가장 먼저 도착하는 마을을 기준으로 배달합니다.

 

해결방법

typealias Parcel = (start: Int, arrival: Int, weight: Int)

let nc = readLine()!.split(separator: " ").map{Int($0)!}
var result = 0
let maxCapacity = nc[1]
var capacity = [Int](repeating: 0, count: nc[0]+1)
var parcels = [Parcel]()
for _ in 0..<Int(readLine()!)! {
    let t = readLine()!.split(separator: " ").map{Int($0)!}
    let parcel = Parcel(start: t[0], arrival: t[1], weight: t[2])
    parcels.append(parcel)
}

parcels.sort { (p1, p2) -> Bool in
    if p1.arrival == p2.arrival {
        return p1.start < p2.start
    } else {
        return p1.arrival < p2.arrival
    }
}

for parcel in parcels {
    var maxWeightInParcel = 0
    for capacityIndex in parcel.start..<parcel.arrival {
        maxWeightInParcel = max(maxWeightInParcel, capacity[capacityIndex])
    }
    // 트럭에 더 실을 수 있는 양
    let remain = min(parcel.weight, maxCapacity - maxWeightInParcel)
    result += remain
    
    for capacityIndex in parcel.start..<parcel.arrival {
        capacity[capacityIndex] += remain
    }
}
print(result)

배운점

도시까지 배달해야 할 택배가 있으면 그걸 다 싣거나 안 싣거나가 아니라 원하는 만큼만 쪼개서 담을 수 있는건데,

이 부분을 놓쳐서 한참을 해맸던 문제였다. 이런 류의 문제가 너무 이해가 안 가서 고통이었는데

드디어 해결... 다음번엔 잘 풀 수 있겠지 ㅠ-ㅠ