백준 8980번 택배(swift) [G3]

그리디 알고리즘

• 매 순간 최선의 선택을 하자

생각회로

• 단순히 그리디하게 정렬(마을에 도착하면 내리고, 도착 순서대로 트럭에 넣음)해서 다 트럭에 넣으면 되는거 아닌가 ?
  -> 당연히 실패 == (처음에 무겁게 싣고, 중간에 작은 거 여러개)
• 실패하는 테스트 케이스 ( 2->3 3->4 를 옮길 수 있으나, 1->4 때문에 못함)
  4 10
  3
  1 4 10
  2 3 10
  3 4 10
  ans : 20
  output : 10
• 진짜 그리디하게
  마을에 도착했을 때, 트럭에 짐보다 먼저 도착하는 짐을 우선으로 싣는다.
  트럭이 다 찼는데, 먼저 도착하는걸 실어야지 -> 나중 도착짐은 버려!

주의사항

• 배운 점 :

  var dict = [Int:Int](\)
  dict[0] = dict[0] ?? 0 + 1  
  dict[0] = (dict[0] ?? 0) + 1

  아래 두 줄은 다른 결과를 유발한다.
  => 초심처럼 괄호를 잘 쓰자.
• loadRestOfLoad 함수를 (남은 짐 싣기) 라는 뜻으로 사용했는데, 좀 더 clean code 하게 써야함. . .

소스코드

import Foundation

struct Bus{
    let max: Int
    var destOfLoad:[Int:Int]
    var sumOfUnload = 0
    var truck = 0
    
    
    mutating func unload(townNum: Int){
        sumOfUnload += destOfLoad[townNum] ?? 0
        truck -= destOfLoad[townNum] ?? 0
        destOfLoad[townNum] = nil
    }
    
    mutating func load(dest: Int, amount:Int){
        var load = amount
        
        if max > truck{
            let canCarry = (max - truck)
            if canCarry >= load{
                carryAt(dest: dest, load: load)
                return
            }else{
                carryAt(dest: dest, load: canCarry)
                load -= canCarry
            }
        }
        loadRestOfLoad(dest: dest, load: load)
    }
    
    mutating func carryAt(dest:Int,load:Int){
        truck += load
        destOfLoad[dest] = (destOfLoad[dest] ?? 0) + load
    }
    
    mutating func loadRestOfLoad(dest: Int, load:Int){
        let loadAfterMe = loadAfterMe(townNum: dest)
        var load = load
        
        for (afterTown,afterLoad) in loadAfterMe{
            if load == 0{
                break;
            }
            
            if afterLoad >= load{
                destOfLoad[afterTown]! -= load
                destOfLoad[dest] = (destOfLoad[dest] ?? 0) + load
                load = 0
            }else{
                destOfLoad[dest] = (destOfLoad[dest] ?? 0) +  afterLoad
                destOfLoad[afterTown] = nil
                load -= afterLoad
            }
        }
    }
    
    mutating func loadAfterMe(townNum:Int) -> [(Int,Int)]{
        destOfLoad.filter{$0.key > townNum}.sorted{ $0.key > $1.key }
    }
    
}



let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, max) = (input[0],input[1])
let M = Int(readLine()!)!

var li = Array(repeating: Array(repeating: 0, count: N), count: N)

for _ in 0..<M{
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    li[input[0]-1][input[1]-1] = input[2]
}

var bus = Bus(max:max, destOfLoad: [Int:Int]())

for i in 0..<N{
    bus.unload(townNum: i)
    for j in 0..<N{
        if li[i][j] > 0{
            bus.load(dest: j, amount: li[i][j])
        }
    }
}

print(bus.sumOfUnload)