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

문제

접근법

5 3
1 3 5 6 10

1, 3 -> 2
3, 5 -> 2
5, 6 -> 1
6, 10 -> 4

정리

1. cost 에 list[k+1]-list[k] 를 저장한다. (원생의 키 차이)

2. 저장된 cost 를 역정렬 한다.

3. M-1 만큼 조를 만들기 때문에 cost 를 계산하는 for 문은 M-1 번 부터 시작한다.

코드

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

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

    int[] list = new int[N];

    String[] inputList = br.readLine().split(" ");
    for(int i=0 ; i<N; i++) {
      list[i] = Integer.parseInt(inputList[i]);
    }

    List<Integer> cost = new ArrayList<>();
    for(int k=0; k<N-1; k++) {
      cost.add(list[k+1]-list[k]);
    }
    Collections.sort(cost, Collections.reverseOrder());

    int sum =0;
    for(int i = M-1; i<cost.size(); i++) {
      sum += cost.get(i);
    }
    bw.write(String.valueOf(sum));

    bw.flush();
    bw.close();
    br.close();

  }
}