센서를 수신할 수 있는 수신 가능 영역의 합을 최소화하기 위해 기지국을 설치 시, 그때의 합을 구하는 문제
그리디 개념을 이용하여 해결 할 수 있었다.
📌문제 접근 포인트
1. 먼저 임의의 위치로 섞여 있으므로, 순서대로 파악할 수 있게 정렬해 주자. 2. 문제의 조건에 의하면 K개의 기지국을 설치한다. 즉, 센서들을 K개로 영역을 나눈다는 의미이다. 입력 예제를 예시로 들면, 정렬한 값은 1 3 6 6 7 9이다. 즉 기지국 2개를 수신하기 위해 [1] | [3, 6, 6, 7, 9] // [1, 3] | [6, 6, 7, 9]... 이런 식으로 2개의 영역을 나누겠다는 의미이다. [1, 3] | [6, 6, 7, 9]를 예시로 수신 가능 영역의 합을 구해보면 앞의 영역에서 길이 3-1 =2, 뒤 영역에서 길이 9 - 6 = 3으로 5를 구할 수 있다. 3. 각 길이에 대해 최솟값의 합이 되기 위해선, 각 센서와 다음 센서 간의 위치 차이를 고려해 주자. 예제를 예시로 들면 [2, 3, 0, 1, 2]의 각 센서 간의 차이를 구할 수 있고, 이 길이를 다시 정렬해 보면 [0, 1, 2, 2, 3]을 얻을 수 있다. 이때 각 값은 연결값에 해당하므로, 가장 긴 값을 떼어버린 기준으로 영역을 잡아주면 된다.
그림을 보면, 가장 긴 값인 3을 기준으로 잘라서 영역을 만들면, 합의 길이가 5가 된다. 즉 센서 위치 차이 값들 중에서 K개의 영역을 만들기 위해서 가장 긴 거리를 K-1개만큼 떼어버리면 최소 합의 영역을 구할 수 있다. 4. 위 과정을 구현할 수 있도록 그리디 & 정렬 개념을 활용하여 구성하면 성공
⚙️내가 푼 정답 코드
import sys
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
censer = sorted(list(map(int, sys.stdin.readline().split())))
x = []
for i in range(N-1):
x += [censer[i+1] - censer[i]] # 각센서 간의 차이
x.sort()
print(sum(x[:N-K])) / 가장 긴것 K-1개를 제외한 나머지의 합
댓글