[백준-파이썬] 2212: 센서

전에 한 코테에서 쓴 맛을 본 후로.. 백준에서 문제를 풀 때 분류를 안 보고 있다! 문제 풀이를 생각해낼 때 시간이 더 오래 걸리긴 하지만, 그래도 그만큼 더 생각하게 되는 것 같다!!

문제 보기

이 문제를 풀 때 한 생각들의 흐름, 풀이

1. 한 위치에 여러 센서가 설치될 수 있다. 그렇지만 그럴 때 하나만 고려하면 된다. -> set을 이용해서 중복을 제거함.
2. 각 센서의 번호 같은 건 중요하지 않다. 센서들을 정렬해서 봐야 겠다. -> sort
3. 각 집중국의 수신 가능 영역의 거리 합이 최소가 되려면, 각 집중국 센서 수신 가능 영역의 시작점과 끝점은 센서 있는 곳인 게 좋겠다.
4. 각 집중국 센서 수신 가능 영역이 조그마한 게 좋다 -> 센서 사이 간격이 큰 순서대로 K-1개 없애자!!
5. 그리고 나머지 간격들을 더하면 정답이다.

사실 전에 비슷한 문제를 푼 적이 있어서 4번 생각을 한 이후로는 쉽게 풀었던 것 같다.
그래도 여기까지 생각한 게 뿌듯하다..ㅎㅎ

코드

import sys

input = sys.stdin.readline

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

sensors = list(set(sensors)) # 중복 제거
sensors.sort() # 정렬

# 각 수의 간격 구하기 -> 큰 순서대로 없애기 -> 나머지의 합
distances = []
for i in range(len(sensors)-1):
    distances.append(sensors[i+1]-sensors[i])

distances.sort(reverse=True)

print(sum(distances[K-1:]))

 

생각의 흐름이 담긴 종이.. 가운데 커피 자국이 있다.