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 을 사용했다.