[백준] 행복 유치원 13164 자바

전형적인 그리디유형의 문제입니다.

모르면 어지간해서는 절대 못풀고, 알면 쉽게 풀 수 있는 문제입니다.

 

난이도 측정이 심하게 잘못되어서 원래 실버2? 쯤에 있었는데, 이 문제는 이후에 골5쯤에서 나오는 센서와 동일한 문제입니다.

 

바로 앞에 있는 숫자와의 차를 모두 배열에 집어넣습니다.

이는 새로운 배열에 할당한다고 생각하시면 됩니다. (코드에서는 배열을 재활용했음)

 

배열을 모든 인덱스에 대해서 2개짜리 묶음으로 묶었다고 생각하시면 편합니다.

그리고 그 묶음에서 n-k만큼 뽑으면 됩니다 ( 묶음끼리 겹치게 되면 한묶음이 된다고 생각! )

 

그림그려보면 이해가능하지만, 일반인의 머리로는 백지상태에서 절대로 쉽게 풀 수 있는 문제가 아닙니다.

이러한 유형은 만났다면, 반드시 풀이를 기억해서 또 만나면 똑같은 방법으로 혹은 활용해서 풀면 됩니다. 

좌절 ㄴ

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 행복유치원 {
	
	static int[] arr;
	static int n,k,res;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		k =  Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		arr = new int[n];
		arr[0] = Integer.parseInt(st.nextToken());
		
		for(int x= 1; x<n; x++) {
			arr[x] = Integer.parseInt(st.nextToken());
			arr[x-1] = arr[x] - arr[x-1]; 
		}
		
		Arrays.sort(arr);
		
		for(int x=0; x<n-k; x++) {
			res+=arr[x];
		}
		System.out.println(res);
		
	}

}