Leetcode 를 풀어 보았다.

1066. Campus Bikes II

worker - bike 쌍을 만들면서 맨하탄 거리 합의 최소를 찾아야 한다.

n, m < 10 인 제한이라 그냥 노가다로 때려 박았다.

var dic = [String: Int]()

func key(_ w: [[Int]], _ b: [[Int]]) -> String {
    w.description + b.description
}

func d(_ w: [Int], _ b: [Int]) -> Int {
    abs(w[0] - b[0]) + abs(w[1] - b[1])
}

func assignBikes(_ workers: [[Int]], _ bikes: [[Int]]) -> Int {
    if bikes.isEmpty || workers.isEmpty {
        return 0
    }

    if let v = dic[key(workers, bikes)] {
        return v
    }

    let n = workers.count
    let m = bikes.count
    let res = (0..<m).map { i -> Int in
        let w = Array(workers[1..<n])
        let b = Array(bikes[0..<i]) + Array(bikes[(i+1)..<m])
        return assignBikes(w, b) + d(workers[0], bikes[i])
    }.min()!

    dic[key(workers, bikes)] = res

    return res
}

dp 문제로 Memoization 을 사용했다.