파이썬 백준 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
'공부하기 > 백준' 카테고리의 다른 글
[Python] 백준 풀기 2217 - 로프 (0) | 2022.12.10 |
---|---|
[Python] 백준 풀기 1789 - 수들의 합 (0) | 2022.12.09 |
[Python] 백준 풀기 12904 - A와 B (0) | 2022.12.07 |
[Python] 백준 풀기 16953 - A → B (0) | 2022.12.06 |
[Python] 백준 풀기 1026 - 보물 (0) | 2022.12.05 |