[백준] 2212 센서 (python 파이썬)

2212번: 센서

---

문제 해석을 잘해야 하는 문제.

---

아이디어

먼저 문제가 요구하는 것을 이해하는 게 필요하다. 
 
문제에서는 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하라고 했다.
이는 아래 예제를 보며 설명해 보면,
 

 
이런 식으로 각 센서들을 커버할 수 있는 최소 영역의 크기를 구하면 된다. 그림을 보면 알다시피 문제의 답을 구할 때 센서의 위치는 겹쳐도 상관없다.
 
문제를 해결하려면, 센서들의 거리가 가장 먼 곳부터 차례대로 지워주면 된다. 예를 들어 위의 그림에서 센서들은 처음에 1 - 9 범위에 전부 있다. 여기서 3과 6의 센서가 가장 멀리 떨어져 있으므로 이곳을 비워주면 1 - 3, 6 - 9 두 개의 집중국으로 모든 센서를 최소 영역으로 커버할 수 있다.

 

이런 식으로 이 문제는 간격이 긴 곳부터 차례대로 지워주면 된다. 집중국의 개수가 K개 이므로 K - 1번 반복해서 지워주면 된다.

 

그리고 만약 집중국 개수가 센서 개수보다 많거나 같으면(K >= N) 따로 계산 필요 없이 0을 출력해 주면 된다. 각각의 센세들은 전부 커버 가능하기 때문.

---

전체 코드

diffList = [] # 각 센서의 거리 차이 저장

N = int(input())
K = int(input())

sensorList = [int(x) for x in input().split()]

if K >= N:
    print(0)
    exit()

sensorList.sort() # 센서 위치 정렬

for i in range(1, N):
    diffList.append(sensorList[i] - sensorList[i - 1])

for _ in range(K - 1):
    diffList[diffList.index(max(diffList))] = 0

print(sum(diffList))

---

코드 설명

sensorList.sort() # 센서 위치 정렬

for i in range(1, N):
    diffList.append(sensorList[i] - sensorList[i - 1])

 센서들의 거리차를 계산하기 위해 먼저 정렬하고 각 센서들의 거리차를 계산해 준다.

 

for _ in range(K - 1):
    diffList[diffList.index(max(diffList))] = 0
    
print(sum(diffList))

거리차가 가장 많이 나는 것부터 K - 1 번 제거해 준다.