백준 13164번

문제

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

알고리즘

1. 그리디 알고리즘

2. 정렬

풀이

티셔츠 제작 비용은 "각 조의 최대 키와 최소 키의 차이"이므로 이 차이를 최소화하는 것이 목표이다.

1. 조를 나누는 위치 중요
   • 조를 나누는 위치마다 새로운 그룹이 시작되고 그룹 간의 비용 합계에 영향을 준다.
2. 두 키의 차이 핵심
   • 인접한 두 원생의 키 차이를 구하고 큰 차이가 발생하는 곳에서 조를 나누면 전체 비용을 줄일 수 있다.

1. 차이 배열 생성

원생들의 키 배열에서 인접한 원생들 간의 키 차이를 계산한다.
예를 들어 키 배열이 [1, 3, 5, 6, 10]이라면 차이 배열은 [2, 2, 1, 4]가 된다.

 

2. 조 나누기 (K개의 그룹 만들기)

K개의 조로 나누기 위해서는 K-1번의 구분점을 선택해야 한다.
구분점으로는 "차이 배열에서 가장 큰 값"을 선택한다. 큰 값에서 나누면 전체 비용 합계를 최소화할 수 있다.

예를 들어:

• 차이 배열 [2, 2, 1, 4]에서 가장 큰 차이 4를 기준으로 나누면, 비용을 줄일 수 있다.

3. 비용 계산

차이 배열을 내림차순으로 정렬한 후 가장 큰 값들을 제외하고 나머지 값들의 합을 계산하면 전체 최소 비용을 구할 수 있다

코드

public class Main {
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(stringTokenizer.nextToken());
			int K = Integer.parseInt(stringTokenizer.nextToken());
			StringTokenizer people = new StringTokenizer(br.readLine());
			List<Integer> peopleSubList = new ArrayList<>();
			int pre = Integer.parseInt(people.nextToken());
			for (int i = 0; i < N - 1; i++) {
				int cur = Integer.parseInt(people.nextToken());
				peopleSubList.add(cur - pre);
				pre = cur;
			}
			int sum = peopleSubList.stream()
				.sorted(Comparator.comparing(integer -> -integer))
				.skip(K - 1)
				.mapToInt(value -> value)
				.sum();

			System.out.println(sum);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}