[Python] 백준 2212 센서

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

 

문제 분석

• 도로 위 N개의 센서를 설치
• 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우려고 하는데 K의 집중국을 세울 수 있다.
• 각 집중국은 센서의 수신 가능 영역을 조절할 수 있다.
• 집중국의 수신 가능 영역 : 고속도로 상에서 연결된 구간으로 나타나게 된다.
• N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며
• 집중국의 수신 가능 영역의 길이의 합을 최소화
• 직선의 고속도로
• 센서들은 직선 위의 한 기점인 원점으로부터 정수 거리의 위치에 놓여 있다.
• 각 센서의 좌표는 정수 하나로 표현
  
  
• 각 좌표 사이에 빈 칸 하나?

 

풀이

• 어떻게 집중국의 수신 가능 영역의 길이의 합을 최소화할 수 있을까?
• 가까운 센서들끼리 묶어서 집중국이 관리를 해야 수신 가능영역의 거리의 합의 최솟값이 된다.
• k개에 대해 최대한 포함하도록 집중국을 세워야 한다.
• 특정 위치에 집중국 k개를 두었을 때 수신 가능 영역들의 합
• 각 경우에 대한 최적해 → 그리디
• 각 센서마다의 간격을 구하고, 그 중 가장 긴 거리를 기준으로 k등분

 

코드 설계

• 입력받은 센서에 대해 정렬
• 각 센서에 대해 간격 구하기
  
  
• k개로 나누기 위해 k-1개 만큼의 거리가 큰 센서 위치 찾기
• 해당 위치들은 끊어지고 / 각 위치들에 대해 - 가장 작은 거리의 위치 찾기

 

정답 코드

실패..

import sys
input = sys.stdin.readline

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

r_dic = {} # 각 센서마다의 간격 (도착 센서 index : 거리)
r_list = []
for i in range(1, n) :
    r_dic[i] = abs(sensors[i] - sensors[i-1])
    r_list[i].append(abs(sensors[i] - sensors[i-1]))

# k-1개만큼 간격이 큰 센서의 위치 찾기
location = []
for i in range(k-1) :
    max_distance = max(r_list)
    max_idx = r_list.index(max_distance)
    location.append(max_idx) # 두 센서 중 나중 센서의 위치 반환 (i-1, i)

print(location)

# dis_k = []
# for j in range(n) :

 

다른 정답 코드 1

import sys
input = sys.stdin.readline

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

x = []
for i in range(n-1) :
    x += [sensor[i+1] - sensor[i]] # 센서간의 차이
    
x.sort()
print(sum(x[:n-k])) # 가장 긴 것 k-1개를 제외한 합

 

 

2회차 - 25.04.02

1차 - 틀림

import sys
input = sys.stdin.readline

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

dis = []

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

dis.sort()
print(sum(dis[:k]))

 

2차 - 맞음

import sys
input = sys.stdin.readline

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

dis = []

for i in range(1, n) :
    distance = sensor[i] - sensor[i-1]
    if distance == 0 :
        continue
    dis.append(distance)

dis.sort(reverse=True)
print(sum(dis[k-1:]))

 

왜 k-1 인가

k = 2
가장 거리가 먼 영역을 분해해 2개의 영역으로 나눔
나눠진 두 영역를 커버(수신가능)하기 위한 길이들의 합

k = 5
4개의 큰 영역을 쪼개면 5개의 영역이 됨
따라서 가장 거리가 긴 영역 4개가 사라짐 (k-1)