[백준 13164번] 행복 유치원- java

문제 설명

1. 학생의 수 N, 조의 수 K가 주어진다.

2. N명의 학생은 오름차순으로 주어지고, K개의 조로 나누어야 한다.

3. 티셔츠를 맞추는 비용은 각 조에서 가장 키가 큰 원생과 가장 작은 원생의 차이만큼 주어진다.

4. 최소의 비용을 구하면 되는 문제이다.

 

풀이 과정

 1. 그리디 문제이고, 이 문제랑 거의 똑같은 로직을 사용하면 쉽게 구할 수 있는 문제이다.

 2. 풀이 방법은 거의 똑같은데, 설명하면 이와 같다.

---

A. 학생 수가 순서대로 정리되어 있으므로, N명의 학생에 대해 키 차이를 구해준다.

B. N-1개의 키차이의 배열이 주어질 텐데 이를 우선순위 큐에 하나씩 넣어준다. 우선순위 큐는 내림차순으로 정리된다.

C. K개의 조로 이루어져 있고, 최소의 가격을 구해야 하므로 조를 구할 때 차이가 큰 것들을 하나로 만들면 가격이 0원이 된다. -> 조의 개수만큼 우선순위 큐에서 빼버리면 될것이다.

D. 나머지 우선순위 큐 값들을 더하면 구해진다.

---

 3. 개인적으로 이전 문제는 처음에 구하는 로직을 찾는것은 굉장히 어려웠다. 다만 해당 문제는 쉽게 구했는데, 한 번 이전 문제를 풀어보게 되면 바로 느낌이 오게 되었기 때문이다.. 그래서 한번 제대로 풀어보면 나중에 비슷한 문제가 주어졌을 때 쉽게 구할 수 있을 것이다.

코드

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int K = sc.nextInt();
	if (K >= N){
	System.out.println("0");
	return;
	}
	int children[] = new int[N];
	for(int i=0; i<N; i++) children[i] = sc.nextInt();
	PriorityQueue<Integer> gap = new PriorityQueue<>(Collections.reverseOrder());
	for(int i=0; i<N-1; i++){
	gap.add(children[i+1] - children[i]);
	}
	for(int i=0; i<K-1; i++) gap.remove();
	int sum = 0;
	while(!gap.isEmpty()) sum += gap.poll();
	System.out.println(sum);
	}
	}

view raw 행복 유치원.java hosted with ❤ by GitHub