백준 - 행복 유치원 ( 13164번, JAVA )

Greedy ( https://www.acmicpc.net/problem/13164 )

풀이

• 가장 작은 티셔츠의 합이 되려면 결국 서있는 인접한 사람들의 키차이를 구하고 k개의 조만큼 만들었을때 최소가 되려면 키차이를 내림차순으로 정렬하고 우선순위 큐에서 k-1만큼 빼주면 된다. 한 조건의 대한 수열을 구하고 그때 최적의 해를 찾아야한다는거 기억하자

package problem_solving.greedy;

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class BaekJoon_13164 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int k = Integer.parseInt(sc.next());
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		
		int num = Integer.parseInt(sc.next()) ;
		for(int i= 1 ; i < n ; i++) {
			int su = Integer.parseInt(sc.next());
			pq.offer(su-num);
			num = su ;
		}
		
		while( ( k-1 ) > 0 ) {
			pq.poll();
			k--;
		}
		int sum  = 0 ; 
		while(!pq.isEmpty()) {
			sum+=pq.poll();
		}
		
		System.out.println(sum);
	}

}