백준 2212 센서

작성일 | In |

문제 링크

알고리즘

  • 그리디
  • 정렬


풀이

아이디어를 떠올린다면 풀 수 있는 문제였다. 핵심 아이디어만 알아낸다면 굉장히 쉬운 문제로 바뀌기에 기억에 남는 문제다.

문제를 읽고 곰곰이 생각해보면 n개의 센서를 k개 그룹으로 묶으라는 말이다. 단, 각 그룹의 센서 간의 거리를 최소화 해야 한다.

따라서 센서 간의 거리를 내림차순으로 정렬한 후에 k개의 그룹으로 묶일 수 있도록 (k-1)번 동안 리스트 내의 가장 큰 값을 제거해주면 된다.

서로 간의 거리가 제거 되지 않은, 즉 연결고리가 끊어지지 않은 센서들끼리 묶는 것이다.

  1. 센서와 집중국의 개수가 같다면 각 센서마다 집중국을 배치하면 되니까 0을 출력하면 된다.
  2. 그렇지 않다면 센서의 위치에 따라서 정렬한다.
  3. 리스트를 하나 만들어서 센서 간의 거리를 내림차순으로 정렬해서 저장한다.
  4. 앞에서 만든 리스트의 가장 큰 값을 (k-1)번 제거한다.
  5. 리스트 안에 남은 값들을 합친 값이 답이다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = int(input())
k = int(input())
sensor = list(map(int, input().split()))

sensor.sort()

if k >= n:
    print(0)

else:
    ls = []
    for i in range(1, n):
        ls.append(sensor[i] - sensor[i-1])

    ls.sort(reverse = True)

    for i in range(k-1):
        del ls[0]

    print(sum(ls))