[백준] 13164. 행복 유치원 (JAVA)

이번에 풀어 볼 문제는 < 백준 13164번. 행복 유치원 > 이다.

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

📌 문제 탐색하기

목표

티셔츠를 만드는 최소 비용 구하기

해야 할 것

1. 티셔츠를 만드는 비용이 최소가 되도록 하려면 조를 어떻게 나눠야 할까?

2. 티셔츠를 만드는 비용 출력하기

입력

[첫 줄] 정수 N (원생의 수), K (조의 개수) ( 1 ≤ N ≤ 300,000 , 1 ≤ K ≤ N )

[둘째 줄] 원생들의 키를 나타내는 N개의 자연수, 원생들의 키는 오름차순 정렬되어 있음, 원생의 키는 10^9 이하

출력

티셔츠를 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력하기

아이디어

1. 티셔츠를 만드는 비용이 최소가 되도록 하려면 조를 어떻게 나눠야 할까?

 

티셔츠를 만드는 비용 = ( 각 조의 키 최대값 ) - ( 각 조의 키 최소값 ) 

만약 1명만 포함된 조일 경우 최대값 = 최소값 이므로 비용은 0이 된다.

 

[예제1]의 상황을 살펴보자.

원생들은 1, 3, 5, 6, 10 순으로 정렬되어 있다.

 

티셔츠를 만드는 비용이 최소가 되려면 인접한 원생들 중 키 차이가 큰 원생들을 서로 다른 조로 쪼개야 한다.

[예제1]의 경우,

원생들 :  1     3     5     6     10

키 차이 :    2      2     1     4

 

이므로 6과 10을 일단 다른 조로 쪼개야 한다.

원생들은 오름차순으로 정렬되어 있기 때문에 차이가 가장 큰 인접한 원생들만 쪼개면 그룹 전체의 최대값 - 최소값도 줄어들게 된다.

 

6과 10을 다른 조로 쪼개면 원생들은 (1,3,5,6) 과 (10) 그룹으로 나뉘게 되고 이때의 비용은 5 + 0 = 5 이다.

이때 비용이 계산되는 과정을 살펴보면, 각 그룹의 비용은 인접한 원생들끼리의 키 차이의 합으로 계산된다.

다시 말해 (2+2+1) + (0) 이 되는 것이다.

 

여기서 그룹을 한 번 더 나눠야 한다면, 그 다음으로 키 차이가 큰 원생들을 쪼개야 한다.

그 다음으로 키 차이가 큰 원생들은 (1,3) 과 (3,5) 이다. 둘 다 키 차이는 동일하게 2인데 이 둘 중 어떤 원생들을 쪼개든 결과는 동일하다. 그 이유는 각 그룹의 비용이 결과적으로 인접한 원생들끼리의 키 차이의 합으로 계산되기 때문이다.

(1,3) 을 쪼개서 그룹을 (1),(3,5,6),(10) 으로 나누어도 비용의 합 = (0)+(2+1)+(0) = 3 이 되고,

(3,5) 을 쪼개서 그룹을 (1,3)(5,6),(10) 으로 나누어도 비용의 합 = (2)+(1)+(0) = 3 이 된다.

 

다시 말해 이 문제는 목표 그룹 수 k 개가 주어졌을 때, 인접한 원생들의 키 차이 값 중 가장 큰 (k-1) 개를 선택하여 그 차이를 가진 인접한 원생들을 같은 그룹에 속하지 않도록 나눠야 한다.

 

2. 티셔츠를 만드는 최소 비용 출력하기

일단 인접한 원생들의 키 차이 값을 모두 구한 뒤, 그 중 (k-1) 개를 선택하여 제거한다. 

이후, 남은 키 차이 값을 모두 합하면 구하고자 하는 최소 비용이 나오게 된다

 

📌 코드 설계하기

1. input 입력을 받는다.

2. 인접한 원생들의 키 차이 값을 계산하여 리스트 diff 에 넣는다. ➡️ O(N-1)

3. diff를 내림차순으로 정렬한다. ➡️O(NlogN)

4. diff의 k-1번째 원소부터 끝 원소까지 모두 더한 뒤 출력한다. ➡️O(N-(k-1))

 

➡️ 전체 코드의 시간복잡도는 O(N) + O(NlogN) + O(N)

➡️ N의 최대값 = 300,000 이므로 전체 연산은 시간내에 수행 가능하다.

 

📌 정답 코드

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

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

        String[] firstLine = br.readLine().split(" ");
        int N = Integer.parseInt(firstLine[0]);
        int K = Integer.parseInt(firstLine[1]);

        String[] secondLine = br.readLine().split(" "); // N개의 원소

        List<Integer> diff = new ArrayList<>(); // N-1개의 원소
        for(int i=0; i<N-1; i++){
            Integer height = Integer.parseInt(secondLine[i+1])-Integer.parseInt(secondLine[i]);
            diff.add(height);
        }

        diff.sort(Collections.reverseOrder());

        long result = 0;
        for(int i=K-1; i<N-1; i++){
            result += diff.get(i);
        }

        System.out.println(result);

    }
}

 

📌 알게 된 것

이 문제가 그리디인지 떠올리기 쉽지 않다...