백준 13164 행복 유치원 (Java)

1. 문제 링크

13164번: 행복 유치원

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 입력받을 때 앞선 키와의 차이를 PQ에 넣는다.

2. 차이를 오름차순으로 정렬해서 K개를 빼고 더한 값을 출력한다.

 

중복순열이나 누적합하면 무조건 시간초과라는 생각에 키 차이를 이용했다.

키 차이 순으로 세우고 K개를 빼고 더한다면 가장 큰 차이가 있는 부분을 제외하고 더해

누적합 느낌으로 한 조 안에서의 최대 키와 최소 키의 차이를 구할 수 있다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.io.IOException;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int N = Integer.parseInt(split[0]);
		int K = Integer.parseInt(split[1]);
		int min = 0;
		
		PriorityQueue<Integer> minus = new PriorityQueue<>();
		split = br.readLine().split(" ");
		int temp = Integer.parseInt(split[0]);
		for(int i=1;i<N;i++) {
			int now = Integer.parseInt(split[i]);
			minus.offer(now - temp);
			temp = now;
		}
		
		for(int i=0;i<N-K;i++) {
			min += minus.poll();
		}
		
		System.out.println(min);
	}	
}