2212번: 센서
첫째 줄에 센서의 개수 N(1<=N<=10,000), 둘째 줄에 집중국의 개수 K(1<=K<=1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 이상 있으며
www.acmicpc.net
- 생각
쉽게 생각하면 k개의 집중국으로 모든 센서를 커버할 수 있는 각 집중국 범위의 합을 구하는 문제이다.
그리디로 접근을 했다. 센서의 위치를 정렬하고 서로의 인접 거리를 계산한 뒤 기지국을 인접 거리가 긴 위치 순서대로 K개 배치하면 수신 가능 영역의 거리의 합의 최솟값을 구할 수 있게 된다.
- 예를 들어 N = 6, K = 2 일 경우
- 코드
정답 코드 : 그리디 방식으로 풀어낸 코드이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static int N, K, answer;
private static int[] array;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
private static void SetData() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
K = Integer.parseInt(br.readLine());
answer = 0;
array = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
array[i] = Integer.parseInt(st.nextToken());
Arrays.sort(array);
int[] temp = new int[N - 1];
for (int i = 0; i < N - 1; i++) {
temp[i] = array[i + 1] - array[i];
}
Arrays.sort(temp);
for (int i = 0; i < N - K; i++)
answer += temp[i];
}
}
'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 2580번 : 스도쿠 (0) | 2021.01.08 |
|---|---|
| [BOJ/JAVA] 백준 2239번 : 스도쿠 (0) | 2021.01.08 |
| [BOJ/JAVA] 백준 14226번 : 이모티콘 (0) | 2021.01.07 |
| [BOJ/JAVA] 백준 11726 : 2 x n 타일링 (0) | 2021.01.06 |
| [BOJ/JAVA] 백준 11727번 : 2 x n 타일링 2 (0) | 2021.01.06 |
