백준 13164번: 행복 유치원

문제 설명

• https://www.acmicpc.net/problem/13164
• N명의 사람을 K개의 그룹으로 나눕니다.
  각 그룹의 점수는 '그룹 내 가장 큰 숫자 - 그룹 내 가장 작은 숫자' 입니다.
  전체 그룹의 점수가 최소가 되도록 그룹을 나누었을 때 그 점수가 얼마인지 구하는 문제입니다.

접근법

• K개의 그룹을 만든다는 건 K-1개의 구간을 자른다는 것과 동일합니다.
  [1, 3, 5, 6, 10]에서 3개의 그룹을 만드는 건 [1 3 | 5 6 | 10]과 같이 2개의 칸막이(|)를 설치하는 것과 동일합니다.
• 6과 10 사이에 칸막이를 설치하지 않으면 6과 10은 같은 그룹으로 묶입니다. 그렇게 되면 해당 그룹은 6과 10이 최소와 최대가 아니더라도 최소 4 이상의 점수를 가집니다.
  [1 3 5 | 6 10 |] -> 6과 10이 포함된 그룹은 4점
  [1 3 | 5 6 10 |] -> 6과 10이 포함된 그룹은 5점
  [1 | 3 5 6 10 |] -> 6과 10이 포함된 그룹은 7점
  [| 1 3 5 6 10 |] -> 6과 10이 포함된 그룹은 9점
  그렇기 때문에 인접한 두 숫자의 차이가 큰 부분에 칸막이를 설치하는 게 이득입니다.
• 저는 여러 구간을 표현할 때 list에 구간값을 모두 넣고 별도로 처음값과 끝값을 넣은 뒤 두개씩 꺼내는 방식을 선호합니다.
  ex) [1,2,3,4,5,6,7,8,9,10]에서 5~6사이, 그리고 1~2사이에 칸막이를 설치했다면 ([1|2,3,4,5|6,7,8,9,10]) 구간값인 5,6,1,2 그리고 시작값과 끝값인 1,10을 list에 넣어 {5,6,1,2,1,10}을 만듭니다. 이를 정렬하면 {1,1,2,5,6,10}이 되고 여기서 2개씩 값을 꺼낸 1~1, 2~5, 6~10이 구간이 됩니다.

정답

import java.util.*;
import java.io.*;

public 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[] arr =new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		// 인접한 숫자들 중 서로의 차이가 큰 값을 찾기 위한 pq
		PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a,b)->b[2]-a[2]);
		for (int i = 0; i < N-1; i++) {
			pq.add(new int[] {arr[i],arr[i+1],Math.abs(arr[i]-arr[i+1])});
		}
		
		
		// ArrayList면 remove에 대해 O(n)이 걸려서 시간초과
		// O(n)인 이유는 뒷에 값을 앞으로 한칸씩 땡겨야 하기 때문
		List<Integer> edgePoint = new LinkedList<Integer>(); 
		
		edgePoint.add(arr[0]); // 시작값;
		edgePoint.add(arr[N-1]); // 끝값;
		
		int cnt = K-1; // 그룹이 K개 -> K-1개의 구간을 자르면 K개의 그룹이 생성됨
		while(--cnt>=0) {
			int[] now = pq.poll();
			edgePoint.add(now[0]);
			edgePoint.add(now[1]);
		}
		Collections.sort(edgePoint);
//		System.out.println(edgePoint.toString());
		
		// 정답 출력
		int answer = 0;
		while(!edgePoint.isEmpty()) {
			int a = edgePoint.remove(0);
			int b = edgePoint.remove(0);
			answer += b-a;
		}
		System.out.println(answer);
		
	}	
}