백준 - 센서 / Gold 5 / 2212번 / Python

문제 📋

백준 - 센서

풀이 📝

import sys


def solution(n, k, sensors):
    sections = []

    sensors = list(set(sensors))
    sensors.sort()

    if k >= len(sensors):
        return 0

    for i in range(len(sensors) - 1):
        sections.append(sensors[i + 1] - sensors[i])

    sections.sort()

    for _ in range(k - 1):
        sections.pop()

    return sum(sections)


n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
sensors = list(map(int, sys.stdin.readline().split()))

print(solution(n, k, sensors))

풀이를 생각해 내는 것이 어려웠던 그리디 문제이다.
수직선 위에 N 개의 센서들이 있고 이 센서들을 모두 포함하면서
가장 최소 길이인 K 개의 구간들의 합을 구하는 것이다.

먼저 센서들 중 중복되는 것들을 제거한 뒤 각 센서 사이의 거리들을 모아서
sections 리스트에 넣어주고 오름차순으로 정렬해주었다.

그런 다음 K=1 일 때를 생각해 보면 모든 구간을 포함하고 있기 때문에
수신 영역의 길이는 sections 리스트의 전체 합과 같다.

K=2 인 상황은 바로 sections 리스트에서 하나를 골라서 제거하는 것이다.
하나를 제거하게 되면 전체 입장에서는 2개의 구간으로 분리되기 때문이다.

그럼 수신 영역의 길이가 최소가 되게 하려면 어떻게 해야 할까?
바로 매 순간에 가장 길이가 긴 구간을 골라서 제거하면 된다.
해당 메커니즘을 K-1 번 반복한다.

추가적으로 K가 N보다 클 때에는 센서가 있는 자리에
수신영역이 0인 집중소를 배치하면 되기 때문에 길이의 합은 0이다.