https://www.acmicpc.net/problem/2212
2212번: 센서
첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있
www.acmicpc.net
백준 - 센서 (2212번)
난이도 : Gold 5
알고리즘&자료구조 : Sorting (정렬) & Greedy (그리디)
★ 핵심 Idea ★
◎ 주어진 센서들을 좌표 순서대로 정렬하고,
인접 좌표 간 거리를 구해서 리스트로 만든다.
위의 거리 리스트를 다시 정렬하고,
가장 값이 큰 K-1개를 제외한 나머지 값들의 합이
수신 가능 영역 길이 합의 최솟값이 된다.
< 전체 코드 >
import sys
input = sys.stdin.readline
class Highway():
def __init__(self, N, K):
self.N, self.K = N, K
self.sensors = sorted(map(int, input().split()))
def main():
highway = Highway(int(input()), int(input()))
intervals = [highway.sensors[i] - highway.sensors[i-1] for i in range(1, highway.N)]
intervals.sort(reverse=True)
print(sum(intervals[highway.K-1:]))
if __name__ == '__main__':
main()
'Algorithm' 카테고리의 다른 글
선분 교차 1 (17386번) - 백준 (BOJ) (0) | 2023.09.26 |
---|---|
열쇠 (9328번) - 백준 (BOJ) (0) | 2023.09.23 |
마라톤 2 (10653번) - 백준 (BOJ) (0) | 2023.09.22 |
주식 (12014번) - 백준 (BOJ) (0) | 2023.09.22 |
새로운 게임 (17780번) - 백준 (BOJ) (0) | 2023.09.15 |