[그리디] 코딩테스트 문제 TIL (센서) - 백준 2212번

말하는 감자·2024년 12월 30일

TIL algorithm baekjoon greedy python sorting 그리디 백준 알고리즘 정렬 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

60/67

1. 오늘의 학습 키워드

그리디 알고리즘
정렬

2. 문제: 2212. 센서

단계: 🥇 골드 5단계
주제:
- 그리디 알고리즘
- 정렬
출처: https://www.acmicpc.net/problem/2212

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력

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

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

예제 입력 1

6
2
1 6 9 3 6 7

예제 출력 1

예제 입력 2

10
5
20 3 14 6 7 8 18 10 12 15

예제 출력 2

3. 문제 풀이

Step1. 문제 이해하기

이 문제는 센서의 좌표를 효율적으로 커버하기 위해 최소한의 거리 합을 계산하는 문제입니다.

평면상의 직선인 고속도로 위에 N개의 센서를 직선 위에 한 기점인 원점으로부터 정수 거리의 위치에 놓여 있습니다.
- 따라서, 각 센서의 좌표는 정수 하나로 표현됩니다.
고속 도로 위에 최대 K개의 집중국을 세울 수 있다고 합니다.
- N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이 합을 최소화해야 합니다.

입출력은 다음과 같습니다:

Input:
- 첫째 줄에 센서의 개수 N이 주어집니다. N은 1이상 $10^4$ 이하입니다.
- 둘째 줄에 집중국의 개수 K이 주어집니다. K는 1이상 $10^3$ 이하입니다.
- 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어집니다. 좌표의 절댓값은 $10^6$ 이하라고 합니다. 이뜻은 음수도 올 수 있다는 것을 의미합니다.
Output:
- 첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력합니다.

Step2. 문제 분석하기

일단 예시를 통해 어떠한 조건이면 최소한의 거리 합을 구할 수 있을지 알아보도록 하겠습니다.

첫 번째 예시는 다음과 같습니다.

N = 6, K = 2
센서의 좌표: 1, 6, 9, 3, 6, 7

위 그림처럼 거리 합의 최솟값은 5가 나옵니다. 뭔가 느낌이 오시나요?

K개의 집중국이 주어지기 때문에 K개의 그룹으로 나누어야 합니다. 다음, 그룹간의 거리를 최소화하기 위해서는, 가장 긴 거리는 끊어야 합니다.

즉, 위 그림에서는 [1, 3] 그룹, [6, 8]그룹에 집중국이 1개씩 배치되었습니다. 만약 그룹이 [1, 3], [3, 9]였다면 훨씬 거리가 더 멀어졌겠죠?

그룹의 위치를 배정하려면 각 센서들간의 거리차를 살펴봐야 합니다. 다음 최소 거리들이 K개가 될때까지 상위 거리 값들은 제외하면 됩니다.

이것을 수행하려면 우선, 주어진 센서 좌표들을 오름차순으로 정렬해야 합니다.

그 다음 각 센서들간의 거리를 구합니다.

마지막으로 N-K개의 거리합들이 정답이 됩니다!

바로 코드 설계를 해보도록 하겠습니다.

Step3. 코드 설계

센서를 정렬합니다.
인접 센서 간의 거리를 계산합니다.
거리를 정렬하고 , N-K 개수만큼의 거리를 확보합니다.
남아 있는 거리의 합을 출력합니다.

Step4. 코드 구현

import sys
N = int(sys.stdin.readline().strip())
K = int(sys.stdin.readline().strip())
sensors = list(map(int, sys.stdin.readline().split()))
def sol(N, K, sensors):
    sensors.sort()
    distances = []
    for i in range(1, N):
        distances.append(sensors[i] - sensors[i - 1])
    distances.sort()
    return sum(distances[:N - K])
print(sol(N=N, K=K, sensors=sensors))

코드 설명:
1. 정렬:
  - 센서 좌표를 오름차순으로 정렬합니다. 이는 그룹화를 하기 위해 각 센서 간의 거리를 순차적으로 계산하기 위함입니다.
2. 인접 거리 계산:
  - 인접한 센서 간의 거리 차이를 계산하여 distances 리스트에 저장합니다.
  - 이 리스트는 집중국을 배치했을 때 각 센서를 연결하는 거리입니다.
3. 최대 거리 제거:
  - distances를 오름차순으로 정렬하고, 가장 긴 K-1개의 거리를 제거합니다.
  - 왜냐하면 최대한 멀리 떨어진 구간을 잘라내야 집중국의 수신 가능 영역의 합이 최소화되기 때문입니다.
  
  3. 거리 합 계산:
- 남아 있는 거리들의 합을 구하면, 최소화된 수신 가능 영역의 길이 합을 구할 수 있습니다.
1. 결과 출력:
  - 결과적으로, sum(distances[:N - K])는 최종적인 최소 거리 합을 반환합니다.
시간 복잡도: $O(N \log N)$ , N의 제한 조건(N ≤ 10,000)에 대해 충분히 효율적입니다.
결과: