JOI 2018, 2018camp contest4 problemB- 난로 > 문제은행 : 정보올림피아드&알고리즘




3160 : 난로

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
24 회   
시도횟수
132 회   

문제

조이의 집에는 난로가 하나 있다

조이는 추위에 강하기 때문에 집에 혼자 있을 때는 난로를 켜지 않아도 되지만, 손님이 오면 난로를 켜야 한다.

 

오늘, 조이의 집에는 N명의 손님이 온다

i번째 (1 i N) 손님은 시간 T_i에 와서 시간 T_i + 1에 나간다

같은 시간에 2명 이상의 손님이 조이의 집에 있는 경우는 없다.

조이는 임의의 시간에 난로를 껐다 켰다 할 수 있다

그러나 난로를 켤 때마다 성냥을 하나씩 써야한다

조이는 성냥을 K개밖에 가지고 있지 않기 때문에, K번만 난로를 켤 수 있다

하루의 시작에는 난로가 꺼져있다

또한 난로는 켜져있는 시간만큼 연료를 소비하기 때문에, 난로를 잘 조작하여 난로가 켜져있는 시간을 최소로 하고 싶다.

 

조이의 방에 오는 손님의 정보와 조이가 가지고 있는 성냥의 개수가 주어졌을 때, 난로가 켜져있는 시간의 최솟값을 구하자. 


입력형식

첫 번째 줄에 두 개의 자연수 N과 K가 공백을 사이에 두고 주어진다. N은 손님의 수를, K는 조이가 가지고 있는 성냥 개수를 의미한다.

두 번째 줄부터 N개의 줄에 손님의 방문 시간을 나타내는 자연수 T_i가 주어진다.

i번째 손님은 T_i시간에 들어와 T_i + 1시간에 나간다. 

 

[제한] 

1 ≦ N ≦ 100,000 1 ≦ K ≦ N 1 ≦ T_i ≦ 1,000,000,000 (1 ≦ i ≦ N) T_i < T_(i +1) (1 ≦ i ≦ N – 1) 

 

1번 부분문제 (20점) 

• N ≦ 20 

• 1 ≦ T_i ≦ 20 (1 ≦ i ≦ N) 

 

2번 부분문제 (30점) 

• N ≦ 5,000 

 

3번 부분문제 (50점) 

• 추가 제한은 없다.


출력형식

첫 번째 줄에 난로가 켜져있는 시간의 최솟값을 나타내는 숫자 하나를 출력한다.

입력 예

3 2
1
3
6

출력 예

4

입력 예

3 1
1
2
6

출력 예

6

입력 예

3 3
1
3
6

출력 예

3

입력 예

10 5
1
2
5
6
8
11
13
15
16
20

출력 예

12

Hint!

1번 예제에서는 조이의 방에 3명의 손님이 온다.

다음과 같이 난로를 조작하면 손님이 있는 동안 난로가 켜져있고, 난로를 켜는 횟수는 2 회이며, 난로가 켜져있는 시간은 총 (4 - 1) + (7 - 6) = 4이다. 

• 첫 번째 손님이 오는 시간 1에 난로를 켠다. 

• 두 번째 손님이 나가는 시간 4에 난로를 끈다. 

• 세 번째 손님이 오는 시간 6에 난로를 켠다. 

• 세 번째 손님이 나가는 시간 7에 난로를 끈다. 난로가 켜져있는 시간을 4보다 짧게 만들 수 없기 때문에 4를 출력한다. 

 

2번 예제에서는 조이가 난로를 딱 한 번 켤 수 있기 때문에, 첫 번째 손님이 오는 시간 1에 난로를 켜고 3번째 손님이 나가는 시간 7에 난로를 끄면 된다. 손님이 나가는 시간과 그 다음 손님이 들어오는 시간이 일치하는 경우가 있음에 유의하라.

 

3번 예제에서는 손님이 도착 할 때마다 난로를 켜고 손님이 나갈 때마다 난로를 끄면 된다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP