공부하기/백준

[Python] 백준 풀기 2212 - 센서

XEV 2022. 12. 8. 22:56

파이썬 백준 2212번

골드 5

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

 

2212번: 센서

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있

www.acmicpc.net

 

 

 

 

 

문제 보기

분류: 그리디 알고리즘, 정렬

 

 

 

 

 

문제 풀기

예제 입력 1 번에 대한 경우를 그림으로 나타내면 위와 같다.

집중국이 커버칠 수 있는 최소한의 거리를 찾으면 가장 넓은 구간 3 을 제외하고 2, 1+2 를 선택하여 최솟값을 이루는 집중국을 위치시킬 수 있다.

 

 

임의로 주어진 센서의 순서를 오름차순으로 정렬을 하고, 그 숫자(센서) 간의 간격을 모두 정리를 한다.

제일 거리의 차가 큰 값은 집중국에서 커버치지 않도록 하여 최솟값을 정하는 데 있어 빠지게 한다. 이는 정렬 저장된 거리 값 리스트 dist_ls 에서 뒤부터 K-1 개를 제거한다고 보면 된다.

따라서, dist_ls[:N-K] 구간의 합을 통해 최솟값을 구할 수 있다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline
def fnMinimumDistance(N, K):
dist_ls = []
sensor_ls.sort()
# print(sensor_ls) # test print
for i in range(0, N - 1):
dist_ls.append(sensor_ls[i+1] - sensor_ls[i])
# print(dist_ls) # test print
dist_ls.sort()
# print(dist_ls) # test print
# print(dist_ls[:N-K]) # test print
print(sum(dist_ls[:N-K]))
if __name__ == "__main__":
N = int(inputdata().strip())
K = int(inputdata().strip())
sensor_ls = list(map(int, inputdata().split()))
fnMinimumDistance(N, K)

 

 

 

 

 

추가 하기

import sys
inputdata = sys.stdin.readline
def fnMinimumDistance(N, K):
dist_ls = []
sensor_ls.sort()
print(sensor_ls) # test print
for i in range(0, N - 1):
dist_ls.append(sensor_ls[i+1] - sensor_ls[i])
print(dist_ls) # test print
dist_ls.sort()
print(dist_ls) # test print
print(dist_ls[:N-K]) # test print
print(sum(dist_ls[:N-K]))
if __name__ == "__main__":
N = int(inputdata().strip())
K = int(inputdata().strip())
sensor_ls = list(map(int, inputdata().split()))
fnMinimumDistance(N, K)
# 6
# 2
# 1 6 9 3 6 7
# [1, 3, 6, 6, 7, 9]
# [2, 3, 0, 1, 2]
# [0, 1, 2, 2, 3]
# [0, 1, 2, 2]
# 5
# 10
# 5
# 20 3 14 6 7 8 18 10 12 15
# [3, 6, 7, 8, 10, 12, 14, 15, 18, 20]
# [3, 1, 1, 2, 2, 2, 1, 3, 2]
# [1, 1, 1, 2, 2, 2, 2, 3, 3]
# [1, 1, 1, 2, 2]
# 7