백준_2212 센서(자바) / 그리디 알고리즘

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_2212 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		ArrayList<Integer> arr = new ArrayList<Integer>();
		int[] dif = new int[N-1];
		int ans=0;
		
		if(K>=N) {
			System.out.println(0);
			return;
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i <N; i++) {
			arr.add(Integer.parseInt(st.nextToken()));
		}
		
		Collections.sort(arr);
		
		for(int i = 0 ; i < N-1;i++) {
			dif[i] = arr.get(i+1)-arr.get(i);
		}
		Arrays.sort(dif);
		for(int i = 0 ; i < N-K;i++) {
			ans+=dif[i];
		}
		System.out.println(ans);
		
	}
}

 

※ 내 생각

이 문제는 그룹을 짓는 문제입니다.
해결하기 위해서는 위치별, 거리별 정렬이 필요했습니다.

먼저 처음에 K개의 집중국이 센서보다 많으면 0을 출력하고 끝이 납니다.
집중국에서 각각의 센서를 수용할 수 있기 때문입니다.

N-K만큼 뺀 만큼의 차이 즉 차이가 너무 큰 나머지를 빼고 계산해주면 됩니다.