백준 13164번 (java)

백준 13164번 행복 유치원

관찰

1. 완전 탐색 방법은 nCk를 통해 k개의 위치를 기준으로 가장 큰 값과 작은 값을 구해서 차이를 계산해서 최솟값을 찾아야 함
   -> 최악의 경우 n 300000 k 150000 nCk 는 천문학적인 경우의 수..
2. 그리디 방법 오름차순으로 정해져있는 수열에서 칸을 나누고 최소와 최대값 차이를 최소로 만드는 방법
   -> 예시의 1 3 5 6 10 -> 2 2 1 4 인데 칸막이로 가장 큰 수부터 선택해서 4,2를 지워주면 작은 수의 합으로 구간 합이 되어 답이 될 수 있다! 풀어보자!

정답코드

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

public class Main {
	static int n; // 원생 수 300000
	static int k; // 조 갯수 300000
	static int res; // 정답
	static int[] dif; // 차이를 저장한 배열
	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());
		dif = new int[n-1];
		
		// 각 인덱스에 차이를 넣어준다
		st = new StringTokenizer(br.readLine());
		int cur = Integer.parseInt(st.nextToken());
		for(int i=0;i<n-1;i++) {
			int next = Integer.parseInt(st.nextToken());
			dif[i] = next - cur;
			cur = next;
		}
		
		// 배열을 오름차순으로 정렬한다
		Arrays.sort(dif);
		
		// 가장 적은 비용을 구해주기
		res = 0;
		for(int i=0;i<n-k;i++) {
			res += dif[i];
		}
		// 출력
		System.out.println(res);
		
	}

}

풀이

1 3 5 6 10의 차이를 구해주면 2 2 1 4 인데 그리디로 최댓값 부터 칸막이를 쳐주면 된다!

느낀점

범위가 너무 괴랄해서 최적화 의심도 안하고 그리디 접근으로 풀어서 무난하게 풀었다 오히려 범위가 작았다면 오래 걸렸을 듯 하다!