BOJ 15553 : 난로

• 문제 링크 : boj.kr/15553
• 난이도 : G5
• 태그 : 그리디, 정렬

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, k;
    cin >> n >> k;

    int before, input;
    cin >> before;
    vector<int> gap(n-1);
    for(int i = 0; i < n-1; i++) {
        cin >> input;
        gap[i] = input - before - 1;
        before = input;
    }
    sort(all(gap));

    int ans = n;
    for(int i = 0; i < n-k; i++) {
        ans += gap[i];
    }
    cout << ans;

    return 0;
}

---

풀이

성냥이 N개 있다고 가정해보자. 이 경우 답은 N이다.

여기서 성냥이 한 개씩 사라진다고 해보자. 성냥이 N-1개가 되었다면, 난로를 켜두어야 하는 시점을 하나 정해야 한다.

두 친구의 방문 사이에 난로를 켜두어야 하고 이 시점은 다른 것에 영향을 받지 않고 자유롭게 정할 수 있다.

난로를 사용하는 시간을 최소화 하고 싶기 때문에, 방문 간격이 가장 좁은 시점을 선택하면 된다.

성냥이 N개부터 K개가 될때까지 반복하더라도 동일하다.

 

따라서 방문 간격을 오름차순으로 정렬하면 문제를 해결할 수 있다.