[BAEKJOON]2212 센서

문제 요약

• 알고리즘 분류: 그리디, 정렬
• 난이도:Gold5
• 문제내용:
  • N개의 센서와 K개 집중국이 있다.
  • K개의 기지국을 설치해서 송신할수 있도록 최소 거리를 구해라.

• 사이트: https://www.acmicpc.net/problem/2212

2212번: 센서

문제풀이

 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 여기에서 확인 해보면된다.

 문제 접근 방법

 예제 1번을 그림으로 나타낸 것이다. 그림 보면 x 좌표 위치가 일직 선상에 있어서 먼저 아래 그림과 같이 정렬 하면된다.

결과

 그 다음 영역을 나누어야 하는데 그 기준은 각 거리가 가장 긴것을 K - 1 기준으로 나누면 최소 거리가 나온다. 코드로는 위와 같이 구현 하는 방법은 센서 위치를 정렬한 다음 각 센서 거리를 구한 다음 센서 거리를 정렬 해서 가장 큰 것부터 K - 1개까지 빼고 다 더하면된다.

정리

1. 센서 위치들을 정렬한다.
2. 각 센서의 거리를 구한 다음 정렬한다.
3. 큰 순 으로 K - 1개를 합한다.

Code

Python

N = int(input())
K = int(input())
sensor = sorted(list(map(int, input().split())), reverse=True)
distances = []
# 각 센서 간의 거리를 계산하여 내림차순 정렬
for i in range(1, N):
    distances.append(sensor[i - 1] - sensor[i])
distances.sort(reverse=True)

# 가장긴것 제외 하고 합하기
print(sum(distances[K - 1:]))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException{
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		Integer[] sensor = new Integer[N];
        // 입력 받은 센서 위치 정렬
		for(int i = 0; i < N; i++) {
			sensor[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(sensor, Collections.reverseOrder());
		Integer[] distances = new Integer[N - 1];
        
        // 센서 거리 계산해서 정렬
		for(int i = 0; i < N - 1; i++) {
			distances[i] = sensor[i] - sensor[i + 1];
		}
		Arrays.sort(distances, Collections.reverseOrder());
		
        // 거리 긴 것 제외하고 합하기
        int sum = 0;
		for(int i = K - 1; i < N - 1; i++) {
			sum += distances[i];
		}
		System.out.println(sum);
		
	}
	
}