백준 13164: 행복 유치원 (골드 5)
문제 링크: https://www.acmicpc.net/problem/13164
이 문제는 그리디 알고리즘을 사용하여 풀 수 있는 문제다.
처음부터 그리디 문제라는 것을 알고 접근했지만, 생각보다 최적의 선택을 정하는 과정이 쉽지 않았다.
문제 요약
- 총 N명의 유치원생을 키 기준 오름차순으로 세워논 상태에서 원생들을 K개의 조로 나눈다.
➡️ 이때, 각 조마다 가장 키가 작은 원생과 가장 키가 큰 원생의 키 차이를 구하고 조마다의 키 차이를 합산했을 때 최소가 되도록 조를 나눠야 한다.- 위처럼 조를 나눈 뒤, 최소 키차이 합을 출력
문제 접근
처음엔 그리디 알고리즘의 원리인 단계마다 최적의 선택을 한다는 큰 틀로 접근했다.
어떤 단계에서 최적의 선택을 해야 할까? 라는 고민에
유치원생 키가 오름차순 정렬된 상태이니,
맨 처음부터 차례대로 최적의 선택을 하면 되지 않을까? 라고 생각했다.
하지만 이렇게 접근하니 문제가 해결되지 않았다.
조의 개수인 K가 정해져 있기도 하고, 단순히 앞에서부터 차례대로 조를 나누는 방식으로는 최적의 결과에 도달할 수가 없었다.
며칠째 시도해보다가 도저히 안되겠어서 푸신 분이 올려준 힌트를 봤다.
힌트를 보고 조금 충격을 받았는데, 그리디에서 중요한 점은 최적의 선택을 어느 순간에서 할지를 알아내는 것임을 깨달았다.
풀이 아이디어
힌트를 바탕으로 내가 이 문제를 풀어낸 방법은 아래와 같다.
K개의 조를 나눌 위치를 찾는 방식에서 최적의 선택을 하고자 했다.
- 원생들이 나열되어 있을 때 뒤 원생과 키 차이와 해당 원생의 위치를 함께 기록한다.
- 우선순위 큐를 사용해서 키 차이가 가장 큰 위치가 어딘지
K-1개만큼 알아낸다.
(키 차이가 가장 큰 원생끼리 다른 조로 배치해버리면 최소합을 이룰 수 있기 때문!!)
(K-1개인 이유는, 파티션K-1개를 놓아야 K개의 조가 완성되기 때문)- 해당 파티션 위치를 기준으로 조를 이루고 가장 작은 원생과 큰 원생의 키 차이를 계산함.
(예를 들어, 파티션 위치가{3,5}면, →{0,1,2,3},{4, 5},{6, 7, ...}이렇게 3개의 조로 나눔)
최종 풀이 코드 (Java)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] array = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
PriorityQueue<int[]> q = new PriorityQueue<>(((o1, o2) -> o2[0] - o1[0]));
for (int i = 0; i < N - 1; i++) {
q.add(new int[]{array[i + 1] - array[i], i}); // 키 차이가 큰 순으로 내림차순
}
int[] partitions = new int[K - 1]; // 차이가 제일 큰 곳부터 다른 조로 쪼개기 위한 파티션 인덱스를 구함.
for (int i = 0; i < K - 1; i++) {
partitions[i] = q.poll()[1];
}
Arrays.sort(partitions);
int start = array[0];
int result = 0;
for (int i = 0; i < K; i++) {
if (i == K - 1) { // 마지막일 경우 분기처리
result += array[N - 1] - start;
break;
}
result += (array[partitions[i]] - start);
start = array[partitions[i] + 1];
}
System.out.print(result);
}
}
그리디는 쉬운 알고리즘이라고 생각했는데, 이번 문제를 풀면서 생각이 바뀌었다.
그리디 알고리즘의 핵심은 '최적의 선택을 어디에서 할지 정하는 것' 임을 알게 되었고, 그리디 문제를 잘 풀기 위해서는 문제 상황에 따라 최적의 선택 기준을 새롭게 세우는 사고가 중요함을 깨달았다.
더 다양한 유형의 그리디 문제를 풀어보면서 감을 익혀봐야겠다. 😅
