백준 13164, 행복 유치원 - Greedy, 정렬

https://www.acmicpc.net/problem/13164

1. 아이디어

• 인접한 인원의 키 차이가 큰 경우
  => 큰 키의 인원을 1명 조로 분리하여, 비용 합 최소화
• 인접 인원의 키 차이가 큰 순으로 (k-1)개 선택하여 조 분리
  
  

1) 인접한 인원들 끼리의 키 차이를 모두 계산

• List<Integer>에 저장

2) List<Integer> 키 차이 큰 순으로 정렬

3) k개 조로 분리

• 키 차이 큰 순으로 (k-1)개 선택
  => 분리할 위치 (k-1)개 선택

2. 자료구조

• int[] heights: 입력, 정렬된 키 배열
• List<Integer> list: 인접 인원의 키 차이 리스트
  => 키 차이 큰 순으로 정렬

3. 시간 복잡도

• 리스트 정렬: O(n log_2 n)
• 정렬된 리스트 원소 반복문: O(n)

코드

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

public class Main {
	static int n;				// 전체 n명
	static int k;				// 전체 k개 조
	static int[] heights;		// 정렬된 키 배열

	static List<Integer> list = new ArrayList<>();	// 인접 인원 키 차이 리스트
	static int minCostSum;		// 출력, 티셔츠 비용 최소합

	static void solution() {
		// 키 차이 큰 순으로 (k-1)개 제외하고, 나머지 키 차이 값들 모두 더함
		for (int i = k - 1; i < list.size(); i++) {
			minCostSum += list.get(i);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());

		heights = new int[n];
		for (int i = 0; i < n; i++) {
			heights[i] = Integer.parseInt(st.nextToken());
		}

		// 인접 인원 키 차이 리스트 저장 및 정렬
		for (int i = 1; i < n; i++) {
			int diff = heights[i] - heights[i-1];
			list.add(diff);
		}
		list.sort(Comparator.reverseOrder());

		solution();
		System.out.println(minCostSum);
	}
}