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번 예제에서는 손님이 도착 할 때마다 난로를 켜고 손님이 나갈 때마다 난로를 끄면 된다.