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

문제 설명

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

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

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

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

 

풀이 과정

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

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

---

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

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

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

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

---

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

코드