[스위프트][백준 2212][💛골드 5] 센서 (그리디)

🧞‍♂️‍ 난이도

💛 골드 5

🧞‍♂️ 문제

센서

https://www.acmicpc.net/problem/2212

🧞‍♂️ 내 풀이

이 문제는 처음 봤을때 공유기설치 문제랑 비슷하다고 느껴서 바로 파라메트릭 서치로 풀 생각했다.

그게 아니고, 그리디하게 풀어야된다.

1. 각 센서 간의 거리를 구하고,
2. 그걸 내림차순으로 정렬시켜서
3. K 만큼 앞에서 없애주고
4. 합을 구하면 된다

🧞‍♂️ 후기

그리디 문제가 연습이 더 필요한것 같다..뭔가 그리디하게 생각하는 법을 머리가 자연스럽게 못하는것 같다. 에이 그렇게하면 당연히 안되겠지라는 풀이법이 보통 되는게 그리디 문제 같다.

🧞‍♂️ 스위프트 코드

import Foundation
let N = Int(readLine()!)!
let K = Int(readLine()!)!
var nums = readLine()!.split(separator: " ").compactMap{Int($0)}

if K >= N {
    print(0)
    exit(0)
}

nums.sort()
var distances: [Int] = []
for i in 1..<nums.count {
    distances.append(nums[i] - nums[i-1])
}

distances.sort { $0 > $1 }
for _ in 0..<K-1 {
    distances.removeFirst()
}
print(distances.reduce(0, +))

---

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기