[BJ] 15553 : 난로

       문제 요약        

- 문제

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

 

         아이디어        

대전제

1) 난로 켜는 시간을 최소화

2) 모든 친구는 추우면 안됨

 

첫번째 예시에서

친구(1) 가 1에 도착 하니까 1일 때 난로 켜고

 

이후에 가능한 행동 2가지

[1] 친구(1) 나가는 시간 2일 때 난로를 끄던지

[2] 계속 켜고 있다가 친구(2)가 나갈 때 끄던지

 

 

매번 [1] 을 선택하는게 난로 켜는 시간을 최소화할 수 있는데

난로 켜는 횟수(K)가 정해져있으니까

텀 짧은 것부터 N-K개 선택, 이후 최소 시간인 1 * K 더하면 됨

 

         소스코드        

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

public class Main {
	static int N, K; // 집을 방문하는 친구의 수, 성냥의 개수
	static int[] arr;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		int ans = 0; // 난로 켜져 있는 시간의 최솟값
		// 해당 시각에 난로 켜기 -> 난로 계속 껐다 켜는게 최소값 -> 한계(K)가 정해져있음
		// (텀 짧은 것부터 N-k) + 그외 K개 x 1
		int[] near = new int[N - 1];
		for (int i = 0; i < N - 1; i++) {
			near[i] = arr[i + 1] - arr[i];
		}
		Arrays.sort(near);
		for (int i = 0; i < N - K; i++) {
			ans += near[i];
		}
		ans += K;
		System.out.println(ans);
	}
	
}