본문 바로가기

Algorithm

센서 (2212번) - 백준 (BOJ)

https://www.acmicpc.net/problem/2212

 

2212번: 센서

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있

www.acmicpc.net

 

 

백준 - 센서 (2212번)

 

난이도 : Gold 5

알고리즘&자료구조 : Sorting (정렬) & Greedy (그리디)


★ 핵심 Idea ★

 

◎ 주어진 센서들을 좌표 순서대로 정렬하고,

인접 좌표 간 거리를 구해서 리스트로 만든다.

 

위의 거리 리스트를 다시 정렬하고,

가장 값이 큰 K-1개를 제외한 나머지 값들의 합이

수신 가능 영역 길이 합의 최솟값이 된다.

 

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline


class Highway():
    def __init__(self, N, K):
        self.N, self.K = N, K
        self.sensors = sorted(map(int, input().split()))


def main():
    highway = Highway(int(input()), int(input()))
    intervals = [highway.sensors[i] - highway.sensors[i-1] for i in range(1, highway.N)]
    intervals.sort(reverse=True)
    print(sum(intervals[highway.K-1:]))


if __name__ == '__main__':
    main()