시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 947 | 617 | 480 | 66.852% |
구사과의 방에는 난로가 하나 있다. 구사과는 절약 정신이 투철하기 때문에, 방에 혼자 있을 때는 난로를 되도록 켜지 않는다. 구사과는 방에 친구가 왔을 때는 항상 난로를 켠다.
오늘은 N명의 친구들이 구사과의 집에 방문하는 날이다. 구사과는 친구들을 쉽게 구분하기 위해 1부터 N까지 번호를 매겼다. i번째 친구는 구사과의 방에 시간 Ti에 도착하고, 시간 Ti+1에 나간다. 구사과의 방은 좁기 때문에, 한 번에 한 명만 방문할 수 있다. 즉, 방안에는 항상 구사과를 포함해 2명 이하의 사람만 있게 된다.
구사과는 난로를 아무 때나 켤 수 있고, 끌 수 있다. 난로를 켜려면 성냥을 이용해야 한다. 오늘 구사과는 총 K개의 성냥을 가지고 있다. 따라서, 최대 K번 난로를 켤 수 있다. 가장 처음에 난로는 꺼져있다.
구사과는 난로가 켜져 있는 시간을 최소로 하려고 한다. 구사과의 친구들이 도착하는 시간과 가지고 있는 성냥의 개수가 주어졌을 때, 난로가 켜져 있는 시간의 최솟값을 구하는 프로그램을 작성하시오.
첫째 줄에 구사과의 집을 방문하는 친구의 수 N (1 ≤ N ≤ 100,000), 구사과가 가지고 있는 성냥의 개수 K (1 ≤ K ≤ N)이 주어진다.
둘째 줄부터 N개의 줄에는 구사과의 집을 방문하는 친구의 도착 시간 Ti가 i가 증가하는 순서대로 주어진다. (1 ≤ Ti ≤ 1,000,000,000) 동시에 두 명이 방문하는 경우는 없기 때문에, 모든 1 ≤ i ≤ N-1에 대해서 Ti < Ti+1 를 만족한다.
첫째 줄에 난로가 켜져 있는 시간의 최솟값을 출력한다.
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
첫 번째 예제의 경우에는 3명의 친구가 방문한다. 아래와 같이 난로를 켜고 끄면 난로가 켜져 있는 시간이 최소가 된다. 이때, 난로가 켜져 있는 시간은 (4 − 1) + (7 − 6) = 4 이다.
두 번째 예제의 경우에는 난로를 오직 한 번만 켤 수 있다. 따라서, 첫 번째 친구가 도착하는 시간 1에 난로를 켜고, 세 번째 친구가 나가는 시간 7에 난로를 꺼야 한다. 한 친구가 나가는 시간과 다른 친구가 도착하는 시간이 같을 수도 있다.
예제 3의 경우에는 친구가 도착할 때마다 난로를 켜고, 나갈 때 마다 난로를 끌 수 있다.
Olympiad > Japanese Olympiad in Informatics > JOI 2017/2018 1번