백준 - 센서(Swift)

백준 - 센서(Swift)

 

 

 문제 설명

 

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

2212번: 센서

 

 나의 풀이

 

문제를 이해하기 어려웠던 문제다.

기지국을 어떠한 좌표에 설치하고 커버하는 방식인 줄 알았는데 다른 글들을 살펴보니 구간을 커버한다는 말이었다.

사실 집중국의 수신 가능영역은 고속도로 상에서 연결된 구간으로 이루어졌다는 말을 보고 짐작은 했으나 아이디어가 떠오르지 않아서 좌표로 생각한 것 같다.

 

그래서 이 문제는 그리디하게 접근해야하는데, 각 센서들을 오름차순으로 정렬하고 각 센서사이의 거리차를 내림차순으로 둔다.

 

그럼 센서사이의 거리차가 높은 것부터 있게되는데 집중국의 개수-1번만큼 배열에서 빼주면 된다.

 

1 3 6 7 9 를예시로 보면

3-6이 센서사이의 합이 가장 크다. 그럼 이 부분부터 뺴는 것인데 그 이유는 가장 큰 부분을 뺌으로써 {1, 3}, {6, 7, 9}가 묶이게 된다. 이 집합은 각각 2와 3을 커버하기때문에 두개의 합인 5가 되어 최소값이 된다. 

만약 가장 작은 것으로 묶는다면 어떻게 될까? 6과7의 사이는 1이다. 이 부분을 뺀다면 {1, 3, 6}, {7, 9}가 되어 각각 5, 2를 다루게 되고 합은 7이된다. 즉 가장 긴 구간을 분리시키는 지점으로 설정하면 되는 것이다. 

 

import Foundation

let N = Int(readLine()!)!
let K = Int(readLine()!)!
var arr = readLine()!.components(separatedBy:" ").map{Int($0)!}
var distances = [Int]()
arr.sort(by: <)

if K >= N { // 기지국이 센서보다 크거나 같다면 종료
    print(0)
    exit(0)
}

for i in 1..<arr.count {
    distances.append(arr[i]-arr[i-1])
}
distances.sort(by: >)

for i in 0..<K-1 {
    distances.removeFirst()
}

print(distances.reduce(0, +))

 

 

 

 피드백

 

이런 문제는 노트에 이것저것 적어보면서 아이디어를 떠올리는 게 중요한 것 같다. 

각 집중국의 수신거리가 최소값이 되기위해서는 집중국이 어느 구간을 기점으로 나눠져야하는지가 핵심이며 이는 조금만 생각하면 센서사이의 거리가 가장 큰 곳이라는 결론에 도달할 수 있다.