[백준/알고리즘/python/java] 2212번 - 센서

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

처음에 문제 이해를 제대로 못해서 애먹었던 문제다.

처음에 이해한 로직은 이렇다. 

N개의 센서가 있을 때, K개의 집중국을 설치해야 한다. 각 집중국은 센서의 수신 가능역역을 조절하는데, 

각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하면 됐다.

 

그러면, N개의 센서의 위치가 주어지면, 우선 그 위치를 오름차순으로 정렬한다음에,

"하나의 집중국과 센서의 거리가 최소가 되려면" 평균거리로 접근하면 되는 줄 알았다.

K개의 집중국을 설치해야 하므로, 평균적으로 N//K 마다 집중국을 설치하고자 했다.

말로 설명하려니까 이해가 안될 수 있으므로 그림으로 설명해보겠다.

예제 입력1을 기준으로 이해한 그림은 아래와 같다.

이렇게 하면, 예제 입력 1은 만족하는 듯 보였다.

예제 입력 2를 살펴보자.

결과가 7이 아닌 8이 나왔다. 아무리 생각해도 이게 최소인 것 같은데, 왜 8이 될까 생각을 거듭한 끝에, 맨 처음 자리에 집중국을 4위치에 설치하는 것이 아닌 3위치에 설치해야 진짜 최소가 되는 것을 발견했다.

이것을 어떻게 코드화를 할까 고심끝에 나온 코드는 아래와 같다.

import sys
input = sys.stdin.readline

N = int(input())    # 센서의 개수 
K = int(input())    # 짐중국의 개수
sensor_position = sorted(list(map(int,input().split())))    # 센서의 위치 오름차순
group = N // K 

average_position = []
idx = 0
while len(sensor_position) != idx:
    tmp = 0
    for j in sensor_position[idx:idx+group]:
        tmp += j
    average_position.append(tmp//group)
    idx += group
# print(average_position)
answer = 0
start = 0
sensor_position.append(1000000)
for idx,sensor in enumerate(sensor_position[:-1]):
    distance = 10000    # 거리 최댓값으로 초기값 설정
    acceptable = 0 # 하나의 집중국이 몇개의 센서를 수용가능한지 나타내는 변수
    if sensor == start :    # 센서가 똑같은 위치면 패쓰 이미 수신가능영역 계산된 셈
        continue
    for k in average_position:
        if distance >= abs(sensor-k):
            distance = abs(sensor-k)
            acceptable += 1 # 센서 포용가능
            start = sensor # # 센서 최신화
        else:   # 오름차순이기 때문에 나머지는 볼것도 없다.
            break
    if sensor_position[idx+1]-sensor_position[idx] > distance and acceptable==1:
        answer += 0
    else:
        answer += distance
print(answer)

예제 입력1과 예제 입력2 둘다 만족은 하지만, 백준에서 돌려본 결과 오답이 떴다.

거의 다  온 것 같았지만, 접근법을 조금 다르게 가져가야 했다. 

예제입력1이 만족하면, 2가 틀리고, 예제입력2를 만족하면, 1이 틀리는 현상이 계속해서 반복됐다.

 

결국, 구글링을 통해 문제에 대해 이해를 제대로 하고, 로직을 다시 생각해봤다.

문제의 핵심은 바로 집중국이 수용가능한 영역 중에 최소값을 더하는 것이므로

집중국을 위치화 하지말고 수용가능한 영역으로 생각해보면 된다.

 

K개의 집중국을 세우게 되면 집중국과 집중국 사이 빈 공간이 K-1개 생기게 된다.

이 K-1개의 빈 공간을 가장 크게 하면 된다!

예제 입력을 적용한 그림으로 설명하면 아래와 같다.

정리한 최종 코드는 아래와 같다.

import sys
input = sys.stdin.readline

N = int(input())    # 센서의 개수 
K = int(input())    # 집중국의 개수
sensor_position = sorted(list(map(int,input().split())))    # 센서의 위치 오름차순

distance_list = []	# 모든 센서간의 거리 리스트
for idx,sensor in enumerate(sensor_position[:-1]):	
	# 현재 탐색하고 있는 sensor와 다음 센서(sensor_position[idx+1]간의 거리를 더해준다.)
    distance_list.append(sensor_position[idx+1]-sensor)	

# 내림차순 정렬하고 집중국 K개를 설치하므로, K-1개의 구역을
distance_list = sorted(distance_list,reverse=True)[K-1:]    # 큰 것부터 K-1개 슬라이싱(삭제)

# 남아있는 거리 리스트의 합이 최소의 집중국 수용범위 합이다.
answer = 0
for d in distance_list:
    answer += d

print(answer)