[백준] 2212번 센서

www.acmicpc.net/problem/2212

2212번: 센서

 

# 문제 해석

 

문제의 글자 수가 너무나도 길어서 이해하기 다소 난해했지만, 풀어쓰자면 다음과 같다.

 

N개의 센서를 설치하는데 자료를 모으기 위해 집중국을 세운다.

이는 수신 가능 영역을 조절하므로, 즉 센서들간의 범위를 지정해준다는 것이다.

최대 K개의 집중국을 설치하되, 각각의 집중국들의 범위의 합을 최소화시킨다.

 

예를 들어, 6개의 센서가 있고 각각 길이가 1,2,3,4,5,6 이며 2개의 집중국이 있을 때,

<1 2 3> <4 5 6> 이런 식으로 집중국의 범위를 지정한다는 것이다.

 

 

 

# 접근 방법

 

1. 문제에서 '원점으로부터의 정수 거리에 위치한다'라고 명시했으므로, sort() 함수를 이용해 오름차순 정렬을 시행한다.

 

2. 각각의 센서들의 거리 차이를 계산하여 최대값(즉, 가장 거리가 먼 값)을 기준으로 분기한다.

 

3. k=2 일 때는 1개의 분기점, k=3일 때는 2개의 분기점이 생기므로, k-1 개의 최대값을 뺀다.

 

4. 최대값을 제외한 나머지 값을 더하면 최소 길이의 합이 된다.

 

e.g.

1    3    6    6    7    9

   2    3    0    1    2

 

--> <1 3> | <6 6 7 9>

--> 2 + 0 + 1 + 2 = 5 가 최소 길이의 합 

 

 

#코드 (파이썬 3.6)

import sys

n = int(input())
k = int(input())
sensor = list(map(int, input().split()))
sensor.sort()

# 만약 k가 n보다 크다면, 센서마다 중점국이 존재하므로 0이 된다.
if k >= n:
    print(0)
    sys.exit()

sensor_diff = []

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

for i in range(k-1):
    sensor_diff.remove(max(sensor_diff))

print(sum(sensor_diff))

 

k >= n 을 고려하지 않으면 런타임 에러가 나왔다. 아직은 잘 모르지만 저 구문이 없다면 k-1 의 분기점을 구할 때,

k의 최대 입력을 넣어준다면 반복 또한 k-1 개를 실시하기 때문에 스택 크기가 상당히 커지기 때문인 것 같다.

다음부터 문제를 풀 때는 입력받는 값들의 상관 관계를 잘 고려해봐야겠다.

 

그리고 내장 함수인 remove와 max를 사용하여 실행 시간이 길어질 수 있으므로,

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

sensor_diff.sort(reverse=True)

for i in range(k-1):
	sensor_diff[i] = 0
    
print(sum(sensor_diff))

다음과 같이 작성하는게 더 효율적이겠다.