문제
행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.
이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.
제한 조건
- 풀이 시간 : 30분
- 제한 시간 : 1초
입력
- 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다.
- 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다.
- 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다.
- 원생의 키는 109를 넘지 않는 자연수이다.
출력
- 티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.
예시
| 입력 | 출력 |
|---|---|
| 5 3 1 3 5 6 10 | 3 |
풀이
최소 비용이 되도록 조를 짜기 위해서는 키 차이가 곧 티셔츠 제작 비용이라는 점에 주목해야 한다. 결국 최소 비용이 되도록 하기 위해서는 인접 인원의 키 차이가 가장 큰 인원을 기준으로 (k - 1)개만큼 분리하여 k개의 조를 짜면 된다.
우선 인접 인원의 키 차이를 계산하고 정렬하여 k개의 조를 만들고, 각 조원의 max, min 키 차이를 구해야 한다고 생각했다. 그래서 인접 인원의 번호와 키 차이를 가지는 객체를 만들고 정렬을 위해 Comparable을 상속받아 compare 메서드를 구현하여 키 차이 값을 통해 정렬될 수 있도록 했다.
하지만 이런 접근 방식을 통해 조를 만들고 키 차이를 구하는 방식을 매우 복잡하게 만들었고, 제한 시간 안에 풀이를 하지 못했다.
다른 사람의 풀이를 확인해보니 굳이 조를 만들어서 키 차이를 계산할 필요가 없었다. 그냥 각 인원의 키 차이의 합이 결국 해당 조의 가장 키가 큰 사람과 작은 사람의 키 차이가 되기 때문이었다. 풀이를 매우 단순하게 각 인원 간 키 차이 값들 중 차이가 가장 많이 나는 (k - 1)개를 제외한 나머지 값들을 모두 더하면 된다.
그리디 문제들을 풀어보면서 느끼는 중요한 점은 문제에서 제시한 조건 그대로 풀이하는 것이 아닌 최대한 단순하게 해결할 수 있는 방법을 찾는 것 같다.
코드
