[백준] 2212번 : 센서

2212번: 센서

2212번: 센서

🤔 문제분석

센서데이터를 그룹핑 하는 문제로 각각의 센서를 그래프로 생각하고, 양 옆에 이웃하는 센서끼리의 거리를 구한뒤, 가장 긴 거리를 k-1 개를 제거한다면 k개의 그룹이 생성되고 가장 긴 거리를 제거 했기때문에 남은 나머지의 간선을 모두 더한다면 수신가능한 영역의 길이의 합이 나온다.

💻 코드

import sys
input = sys.stdin.readline

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

sensor = list(map(int, input().split()))
sensor.sort()

dist = []
for i in range(1, N):
    dist.append((sensor[i] - sensor[i-1]))

dist.sort()
for _ in range(K-1):
    if dist:
        dist.pop()

if K >= N:
    print(0)
else:
    print(sum(dist))

🎯 피드백 및 개선사항

생각의 발상으로 각각의 센서를 노드로 생각하고, 정렬한뒤에 각 이웃하는 노드끼리 연결한뒤에 가장 긴 간선을 k-1개를 제거한다면 k개의 그룹이 생긴다. 나머지 간선을 더한다면 집중국의 수신가능한 영역의 최소길이가 나온다.