백준_2212_센서 (python)

★ 접근

 센서의 개수 최대 만 + 집중국의 개수 최대 천 + 센서 좌표값 (절댓값) 백 만 + 시간 제한 2초 => 종합적으로 미뤄봤을 때 그리디 알고리즘이 떠올랐다. 근데 도대체 이것을 어떻게 그리디로 풀 것인가? 오랜 시간 생각해서 떠오른 것은 일단 데이터를 정렬하고 index가 1차이 나는 센서끼리 차이를 구해보기로 햇다. 

★ 풀이

 집중국을 하나 설치한다는 것은 모든 센서가 하나의 집중국과 수신한다는 얘기이다. 즉 모든 센서가 하나의 구성이다.

집중국을 두개 설치한다는 것은 센서가 두 개로 나뉘어져서 집중국과 수신한다는 얘기이다. 즉 센서가 두 구성이다.

 

예제 입력 1번을 예시로 들어보면 센서간의 차이가 1,2,2,3이 있다. 여기서 집중국을 두개 설치하는데 둘의 차이가 가장 적은 1을 빼면 센서는 (1 3 6) (7 9)로 나뉘어질 것이다. 여기서 첫 번째 집중국의 거리는 5가 되고 두 번째 집중국의 거리는 2가 된다. 그럼 도합 합은 7이다. 틀렸다.

틀린 예제에서 알 수 있듯이 거리차이가 가장 큰 센서 차이를 빼야 답이 가장 적어진다. 이유는 만약 가장 거리차이가 큰 3즉 (센서 3과 6사이를 갈랐다면)        (1 3) (6 7 9)로 묶인다. 집중국의 수신거리 최소 합은 5가 된다.  

 

[위에 풀이가 이해 안되신 분들을 위한 마지막 설명 ㅠㅠ 여기서는 이해 되시길 바랍니다...  ]

(1 3 6 7 9) 한 묶음으로 존재하던 센서들이 있고 집중국 2개를 설치할 것인데 어느 부분에 갈라야 최소가 되는가? 거리차이가 가장 큰 부분 즉 3과 6 사이 (1 3) (6 7 9)이다. 즉 집중국 - 1만큼 갈라야 하고 그 개수만큼 거리차이가 큰 것 부터 없애고 남은 거리 차이를 더하면 된다.

★ 코드

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())
data = list(map(int,input().split()))
data = list(set(data))
data.sort()
answer = []
for i in range(len(data) - 1):
    answer.append(data[i+1] - data[i])
answer.sort()
if k >= len(data):
    print(0)
else:
    for i in range(k-1):
        answer.pop()
    print(sum(answer))

★ 회고

 접근을 쓰다 만 것에서 알 수 있듯이 감각적으로 차이까지만 구하고 풀지 못했다. 문제를 잘못 이해했다. 집중국을 어느 한 좌표에 설치하고 센서들과의 차이의 합을 구하는 것인줄 알았다. 집중국의 영역을 구하는 것이었다니....

 화이팅!!!