13164번 : 행복 유치원

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

13164번: 행복 유치원

 

 

문제

 

 

코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int arr[] = new int[n-1];
        st = new StringTokenizer(br.readLine(), " ");
        
        int pre = Integer.parseInt(st.nextToken());
        int cur = 0;
        for (int i=0;i<n-1;i++) {
            cur = Integer.parseInt(st.nextToken());
            arr[i] = cur-pre;
            pre = cur;
        }

        Arrays.sort(arr);
        long result = 0;
        
        //조가 k개면 k-1개 버릴 수 있으므로, 작은 값부터 결과값에 더한다.
        for (int i = 0; i < arr.length - (k - 1); i++) {
            result+=arr[i];
        }
        System.out.println(result);
    }
}

 

 

해결방법

조마다 티셔츠를 맞추는 비용은 "조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다."라고 나와있다. 

어떻게 풀지 계속 고민하였다. 모든 경우의 수를 찾는 것은 아닌 것 같아서 메모장에 끄적여보다가 해결방법을 찾았다.

옆 사람과의 키 차이를 저장한 뒤, 그 차이에서 큰 순서대로 K-1개를 제외하고 나머지를 더해주면 문제는 해결된다.

K-1개를 제외하는 이유는 K-1개의 조를 만들면 결국 K개의 조가 생기기 때문이다. 이때, "제외하다"는 제외시킨 사람 혼자 조를 형성한다는 의미이다. 조가 없다면 결국 다 더해져야 하는 값이기에 그중 큰 값 K-1개를 빼면 최솟값이 되는 것이다.

 

input

7 3
1 3 5 6 7 8 10  
 2 2 1 1 1  2    => 옆 사람과의 키 차이에서 큰 순서대로 (3-1)개 제외하여 티셔츠 맞추기