[백준: Python] 2212 - 센서

[문제]

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

문제 난이도에 비해, 설명이 시원하게 와닿지 않은 문제였습니다.

---

[초기화]

    def __init__(self):
        self.n = int(input())
        self.k = int(input())
        self.sensor = list(map(int, input().split()))

---

[풀이]

    def solve(self):
        self.sensor.sort()
        distance = sorted(list(map(lambda i: self.sensor[i + 1] - self.sensor[i], range(self.n - 1))))
        print(sum(distance[:self.n - self.k]))

1. 인접한 센서들의 거리를 계산합니다.
   • 정렬을 하는 이유는 센서들이 순서대로 들어오지 않기 때문입니다.
   • 첫 번째 테스트케이스 기준, 현재 위치한 센서와 우측 센서의 거리를 계산하면 [2, 3, 0, 1, 2]의 거리를 가집니다.
   • 이때, k개의 집중국을 설치하게 되는데, 문제에서 제시된 조건인 최대 k보다 항상 k라고 생각하면 이해가 쉬워집니다.
   • 극단적으로 n개의 센서에 n개의 집중국을 설치하면, 1:1이므로 수신 가능 영역은 0이 됩니다. 그러므로 항상 k개를 설치하는 것이 이득인 것을 알 수 있습니다.
2. 계산된 센서들을 정렬합니다.
   • k개의 집중국을 설치하면, 집중국 간의 거리는 k - 1개가 나옵니다. 이 거리는 수신 거리와 상관없으므로 계산 범위에서 제외합니다.
   • 첫 테스트케이스의 경우 k - 1 = 1, 하나의 집중국 간의 거리가 나오고 가장 큰 값은 3입니다.
   • 이를 토대로 다음과 같이 분할할 수 있습니다.
     [1, 3] | [6, 7, 9]
     (3 - 1) + (9 - 6) = 5
   • 두 번째 테스트케이스입니다.
     센서의 위치를 정리하면 [3, 6, 7, 8, 10, 12, 14, 15, 18, 20]
     센서 간의 거리를 정렬하면 [1, 1, 1, 2, 2, 2, 2, 3, 3]
     k - 1개의 집중국 간 거리를 제거 [2, 2, 3, 3]
     3: [3, 6, 7, 8, 10, 12, 14, 15] | [18, 20]
     3: [3] | [6, 7, 8, 10, 12, 14, 15, 18, 20]
     2: [3] | [6, 7, 8, 10, 12, 14, 15] | [18] | [20]
     2: [3] | [6, 7, 8, 10, 12] | [14, 15] | [18] | [20]
     0 + (12 - 6) + (15 - 14) + 0 + 0 = 7
3. k - 1개의 집중국 간의 거리를 제거하고 남은 값들의 합을 계산합니다.

---

[전체 코드]

class Main:
    def __init__(self):
        self.n = int(input())
        self.k = int(input())
        self.sensor = list(map(int, input().split()))

    def solve(self):
        self.sensor.sort()
        distance = sorted(list(map(lambda i: self.sensor[i + 1] - self.sensor[i], range(self.n - 1))))
        print(sum(distance[:self.n - self.k]))


problem = Main()
problem.solve()

---