[Greedy] 백준 - 센서 2212번

👏 key point

사실 문제를 이해하는 데 있어서 상당히 오랜 시간이 걸린 문제이다.

예를 들어 입력받은 리스트가 1 6 9 3 6 7이고

좌표상으로 표현하면 다음과 같다.

Q. 만약 집중국이 하나라면 어떨까??
A. 1~9까지의 모든 센서들을 감지해야 하므로 수신 가능 영역의 길이는 8이다.

Q. 그렇다면 집중국의 개수가 2개라면 어떨까?

A. 이렇게 구간이 제일 긴 구간을 제외하고 나누게 되면 수신가능 영역의 길이는 5로 가장 짧게 집중국을 설치할 수 있을 것이다.

따라서 필자는 좌표상 평면을 구현하기 위해 센서들을 오름차순으로 정렬하고

바로 옆에 있는 센서들끼리의 거리들을 구하여 배열로 나타낸 distance를 생성하였다. 그리고 그 배열을 다시 정렬하여 가장 큰 값을 빼는 과정을 반복하였다.(k-1번)

그렇게 하여 남은 구간들의 합이 바로 수신 가능한 영역의 최솟값이 된다. 자세한 내용은 코드를 보면 알 수 있다.

🎂 코드

n = int(input())

k = int(input())

sens = list(map(int, input().split()))

if n <= k:
    print(0)

else:    
    #센서들을 오름차순으로 정렬
    sens.sort()

    distance = []

    #distance = 옆에 있는 센서들끼리의 거리들을 구한 배열
    for i in range(1,n):
        distance.append(sens[i] - sens[i-1])

    distance.sort()
    #distance를 정렬하여 k-1만큼 pop
    for _ in range(1,k):
        distance.pop()

    #남은 구간들의 합 = 수신 가능영역의 최솟값
    print(sum(distance))