[baekjoon] 2212. 센서

✅ 문제

 

💡 문제 이해
최대 k개의 집중국의 수신 가능 영역 길이의 합의 최솟값을 구하는 문제
1. 센서를 묶어 k개의 집중국으로 나눔
2. 각 집중국 내의 센서 간 수신거리의 합이 최소가 되는 경우 = 집중국간 경계의 거리가 최대가 되는 경우

 

 

---

 

✅ 풀이

 

문제 자체를 이해하는데 한참 걸렸다.

그리디 알고리즘 방식으로 접근하면 된다고는 생각했지만 실제적으로 구현이 좀 어려웠음

 

💡 문제 풀이 Point

1. 집중국이 k개일 때 집중국 경계 영역은 k-1개
2. 원점으로부터 거리 -> 오름차순 정렬 후 인근 센서 사이 거리 구하기
3. 센서 간 거리를 배열에 담고 오름차순하여 가장 큰 수 k-1개를 제외한 나머지 합을 구하기

 

---

 

아래에 예제 입력 2가지 경우를 모두 그림으로 그려 보았다.

각 센서간 거리를 구한 다음 가장 큰 순서대로 k-1개만큼 경계 거리라고 생각하면 된다.

집중국 내 센서간 거리의 합이 최소가 되어야 하므로 경계로 정한 수만 빼고 다 더해주면 끝!

 

k=2, 집중국 2개, 경계 k-1(1)개

k=5, 집중국 5개, 경계 간 거리 k-1(4개)

 

 

 나의 코드

import sys
input = sys.stdin.readline

# 최대 k개의 집중국의 수신 가능 영역 길이의 합의 최솟값
# 센서를 묶어 k개의 집중국으로 나눔
# 각 집중국 내 센서 간 수신거리 합이 최솟값 = 집중국 경계의 거리가 최대가 되는 경우
# 집중국이 k개일 때 집중국 경계 영역은 k-1개
# 원점으로부터 거리 -> 오름차순 정렬 후 인근 센서 사이 거리 구하기

n = int(input()) # 센서 개수
k = int(input()) # 집중국 개수
sensors = list(map(int, input().split())) # 센서 좌표
sensors.sort() # 가까운 순으로 정렬

distance = []

for i in range(0, n-1):
    distance.append(sensors[i+1] - sensors[i])

distance.sort()
print(sum(distance[:n-k])) # 경계지점 k-1개 제외한 나머지 거리 합