[Python][백준/BOJ] 2212번 : 센서

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

2212번: 센서

 

내 코드

import sys
input = sys.stdin.readline

sensor = int(input())
cnt = int(input())
lo = list(map(int, input().split()))
lo.sort()
dif = []

for i in range(1, sensor):
    dif.append(lo[i]- lo[i-1])
dif.sort()

print(sum(dif[:sensor-cnt]))

 

코드 리뷰

만약 백준에 제시된 예제대로 푼다고 생각해보자.

6
2
1 6 9 3 6 7

이 수가 입력으로 들어갈 것이고, 센서가 설치되어 있는 곳을 1로 표시한다면 다음과 같은 배열이 생성될 것이다.

1	2	3	4	5	6	7	8	9
1	0	1	0	0	1	1	0	1

 

문제에서 요구하는 것은 k개를 설치할 건데, 센서가 포함할 수 있는 범위를 최소로 할 수 있는 위치를 파악하라는 것이다.

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

우선 위치를 정렬하여 파악한다.

for i in range(1, sensor):
    dif.append(lo[i]- lo[i-1])
dif.sort()

그리고 이 dif 함수에는 각 위치의 차를 저장해줄 것이다.

1 6 9 3 6 7를 정렬하면
1 3 6 7 9 가 된다. 각 수의 차를 구하면
[0, 1, 2, 2, 3] 이다.

문제를 접근하는 핵심은 바로 설치된 위치가 멀다면, 크면 클수록 그 거리를 기준으로 설치하는 것을 고려하겠다는 것이다.

[0, 1, 2, 2, 3]이면, 3에 해당하는 것은 3~6까지의 거리이다. 그러므로 가장 차이가 많이 나는 3~6부분을 갈라놓는다.

이렇게 [1 3 ] [6 7 9] 로 나눈다. 

3~6 사이의 거리는 필요없다고 생각하는 것이 곧 dif[:sensor-cnt] 이다. 3은 필요없으니 이를 제외한 [0, 1, 2, 2]만 더하는 것이다.