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

백준 13164번 문제 - 행복 유치원

13164번: 행복 유치원

---

문제 분석

 

• 주어진 N명의 원생들을 K개의 조로 나눈다.
• 나누어진 조 비용 : 조에서 가장 큰 사람 키 - 조에서 가장 작은 사람 
• 나누어진 조 비용의 합을 출력해라

---

해결 키 포인트

• 해결 방식 1 - 실패
  • 최대 차이 값 = (가장 큰 값 - 가장 작은 값) / K
  • 조의 비용이 최대 차이 값을 넘기지 않게만 조를 나누고 그 차이 값들을 더한다
• 해결 방식 2 - 성공
  • 근처 값과의 차이 값을 구하기
  • 차이 값을 오름차순 정렬
  • 인덱스 0번 값 부터 N-K값까지 다 더한다
     | N-K까지가 아니라 K-1까지 값을 다 더해야한다고 생각 해서 좀 해맸다.

---

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        // 원색 수(N)와 조 수(K) 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // 근처 값과의 차이 값
        int [] gaps = new int[N-1];

        // 원생
        int [] people = new int[N];

        // 원생 입력
        st = new StringTokenizer(br.readLine());
        people[0] = Integer.parseInt(st.nextToken());
        for(int i=1;i<N;i++) {
            people[i] = Integer.parseInt(st.nextToken());
            // 차이값 구하기
            gaps[i-1] = people[i] - people[i-1];
        }

        // 차이 값 정렬
        Arrays.sort(gaps);

        // 조 비용 결과 구하기
        int sumCash = 0;
        for(int i=0;i<N-K;i++) {
            sumCash += gaps[i];
        }

        // 출력
        bw.write(sumCash + "\n");
        bw.flush();
        bw.close();
        }
}