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

🌵 문제 분석

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

N명의 원생을 키 순서로 줄세우고 K개의 조로 나눈다.

모든 조의 (가장 큰 키)-(가장 작은 키)의 합을 최소로 할 때, 그 최소값을 구하라.

입력 :

N(원생의 수) K(조의 수)

원생들의 키

5 3
1 3 5 6 10

 

🌵 구현 아이디어

💡 그리디로 풀기

인접한 학생의 키차이를 모두 구해보았다.

👉🏻

 

어디를 나눠서 조의 경계를 만들면 좋을까?

👉🏻 키차이가 가장 많이 나는 두 원생의 사이를 나누기

👉🏻 키차이가 가장 큰 원생들의 조를 다르게 함으로써 한 조 안의 (가장 큰 키)-(가장 작은 키)를 최소화할 수 있다.

✅ 접근 방법

인접한 두 학생의 키차이를 모두 구한 후

그 값이 큰 순서대로 두 명의 원생의 사이를 K-1번 갈라서 조를 나눈다.

예제 :

예제 입력 1의 경우

5 3
1 3 5 6 10

5명의 원생을 3조로 나눠야 한다.

 

1️⃣ 원생 정렬

1 3 5 6 10으로 정렬한다.

2️⃣ 인접한 키차이가 가장 큰 순서로 두 명의 원생의 사이를 K-1번 갈라서 조를 나누기

인접한 원생의 키차이를 구하면 2 2 1 4이다.

그 중 가장 큰 값은 4이므로 4번째, 5번째 원생 사이를 나눠서 두 조로 만든다.

그 다음으로 큰 값은 2이므로 1번째, 2번째 (또는 2번째, 3번째) 원생 사이를 나눠서 세 조로 만든다.

3️⃣ 남은 인접한 키차이를 더해 정답 도출하기

남은 인접한 키차이를 더하면 모든 조의 (가장 큰 키)-(가장 작은 키)의 합과 같다.

2+1=3을 출력한다.

🌵 시간 복잡도

원생을 정렬하는 시간 복잡도 : O(nlogn)

인접한 원생 간의 키차이를 구하는 시간 복잡도 : O(n)

인접한 원생 간의 키차이를 정렬하는 시간 복잡도 : O(nlogn)

나머지 키차이를 더하는 시간복잡도 : O(n-(k-1))

 

전체 시간 복잡도는  O(nlogn)+O(n)+O(nlogn)+O(n-(k-1))

n은 최대 300,000이므로 약 5+300,000+5+300,000=600,010

따라서 주어진 시간(1초) 안에 연산 가능하다.

🌵 알고리즘

그리디 알고리즘

🌵 코드 설계

1. 입력값 받기
   1. int 변수에 N, K값 저장
   2. int[] h 배열에 원생들의 키 저장
2. h배열 오름차순 정렬하여 원생들을 키 순서로 세우기
3. h[i+1]-h[i] (인접한 학생의 키차이)값을 원소로 가지는 diff배열 생성
4. diff배열을 정렬
5. diff의 원소를 작은 것부터 diff.length-(k-1)번 더하기 
   (== 가장 큰 키차이 k-1개 빼고 남은 키차이들 모두 더한 값)
6. 정답 출력

🌵 정답 코드

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

public class Main{
    static int N, K;
    static int[] h, diff;
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        //입력받기
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        h = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            h[i] = Integer.parseInt(st.nextToken());
        }
        
        //키순서로 정렬
        Arrays.sort(h);
        
        //인접한 원생 간 키차이 구하기
        diff = new int[N-1];
        for(int i=0; i<N-1; i++){
            diff[i] = h[i+1]-h[i];
        }
        
        //키차이 정렬
        Arrays.sort(diff);
        
        //키차이가 가장 큰 K-1개 빼고 나머지 키차이 다 더하기
        int ans = 0;
        for(int i=0; i<diff.length-(K-1); i++){
            ans += diff[i];
        }
        System.out.println(ans);
    }
}