[그리디] Python - 2212번, 센서[Grid] Python - 2212번, 센서

www.acmicpc.net/problem/2212

import sys
input = sys.stdin.readline

N = int(input())
K = int(input())
censors = list(map(int, input().split()))
censors.sort()

if N < K:
    print(0)
else:
    distancesBetweenCensors = []
    for i in range(N-1):
        distancesBetweenCensors.append(censors[i+1]-censors[i])
    distancesBetweenCensors.sort()

    for _ in range(K-1):
        distancesBetweenCensors.pop()
    print(sum(distancesBetweenCensors))

센서들을 정렬해서 각 센서 간의 거리를 저장한다.(distancesBetweenCensors)

그리고 집중국이 K개일 때, 방금 저장한 리스트에서 K-1개의 요소들을 제외하고 남은 요소를 모두 더한 값이, 구하고자 하는 값이 된다. 따라서 distancesBetweenCensors를 정렬해주고 가장 큰 요소들을 K-1개 제외해주고, 마지막으로 sum을 구해주는 것이다.

여기에 설명이 빈약한 것 같아 직관적으로 이해할 수 있도록 그림 몇 개를 준비했다.

예시의 경우이다.

감이 오는가? 3이 나온 곳을 기준으로 앞뒤를 묶는 것이다.

만약 K가 3개였다면, 이 경우는 다음과 같다.

두 경우 중 하나이다.

 

사실 나는, 원래 이렇게 가장 긴 거리들을 기준으로 묶어놓고, 바로 위의 경우를 예시로 들면, (3-1) + (7-6) + 9와 같은 식으로 답을 구했었는데, 실은 이럴 필요가 없었다.

이미 각 거리들을 구했었고, 이것들을 더하기만 하면 됐으니 말이다. 2+(0+1)+0처럼 말이다.