[Java] 백준 13164번 - 행복 유치원

문제 링크 : https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

 

문제

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

입력

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.

출력

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

 

---

접근 방법

먼저 같은 조에 속한 원생들은 서로 인접해야 하는 것에 주의하자. 

 

하기의 입력 예시로 생각해보자. 

5 3
1 3 5 6 10

여기서 3개의 조로 원생들을 나누어야 하는데, 같은 조 원생들은 서로 인접해야 하기 때문에

주어진 1 3 5 6 10 에서 2개의 막대기를 원생들 사이에 두면 조건을 만족하면서 조를 나눌 수 있다. 예시는 아래와 같다. 

 

1 |  3  5  |  6  10   => 비용 : 2 + 4 = 6

1  3  |  5  | 6  10   => 비용 : 2 + 4 = 6

1  3  |  5  6  |  10   => 비용 : 2 + 1 = 3 (최저 비용)

 

그렇다면 막대기 K-1개는 어디에 두어야할까? 바로 인접한 원생과의 키차이가 가장 크게 나는 곳에 두어야 한다. 키차이가 가장 크게 나는 곳에 막대기를 두게 되면, 그 키차이(비용)은 제외되어 버리기 때문이다.

위 예시에서 생각해보면 

1 3 5 6 10 일 때, 원생들과의 키차이는 

2 2 1 4 이기 때문에

키차이가 2와 4인 곳에 막대기를 두어야 하는 것이다. 그럼 비용에서 2, 4는 제외되고 2, 1만 남는다. (2+1이 최소 비용)

 

일반화를 해보면 다음과 같다.

1) 인접한 원생들 사이의 키차이를 구한다. 

2) 키차이를 내림차순으로 정렬한다. (위 예시에서는 4 2 2 1)

3) 막대기 K-1개로 조를 나눈다. 즉 내림차순으로 정렬된 수열에서 K-1개를 제외한다.

4) 제외하고 남은 키차이들을 다 더하면 그 합이 티셔츠의 최소 비용이 된다. 

 

 

import java.io.IOException;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class BOJ_13164_행복유치원 {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();
        int answer = 0;
        ArrayList<Integer> tall = new ArrayList<>();
        ArrayList<Integer> subTall = new ArrayList<>();
        
        //키 입력받기
        for(int i = 0; i<N; i++){
            tall.add(sc.nextInt()); 
        }
        //키 차이 구하기
        for(int i = 0; i < N-1; i++){
            subTall.add(tall.get(i+1) - tall.get(i));
        }
        //키 차이 오름차순 정렬
        Collections.sort(subTall);

        //가장 큰 키차이를 K-1개 제외하고 나머지들 더함
        for(int i = 0; i < N-K; i++){
            answer += subTall.get(i);
        }
        System.out.println(answer);
    }
}