[BOJ] 15553번 : 난로 C++ 풀이

간단한 그리디 문제이다. N명이 방에 올 것이고, K번만 난로를 켤 수 있다. 이때 난로가 켜져 있는 시간을 최소로 해야 한다.

상황을 살짝 변형해서 생각해 보자. K번을 언제 켤지 생각하지 않고, 일단 N명이 들어올 때마다 전부 난로를 켤 것이다. 그러면 연결해야 하는 난로의 개수는 N-K개라는 것을 알 수 있는데 이제 이 값을 최소로 만들면 된다.

당연하게도 앞에 있는 사람과 나의 연결 값이 작아야 전체의 값이 작아진다. 따라서 나의 앞사람과 나 사이에 난로가 켜져 있는 시간들을 구하고 전부 배열에 넣어 오름차순 정렬하자. 그다음 앞에서부터 N-K명을 연결해 주면 항상 최소 시간을 유지할 수 있다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 1000000000
#define MOD 1000000009
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
int N, K;
vector<int> v;

void init() {
    cin >> N >> K;
    int last = -1e9;
    for (int i=0; i<N; i++) {
        int x;
        cin >> x;
        v.push_back(x - last);
        last = x+1;
    }
    sort(v.begin(), v.end());
    int answer = N;
    for (int i=0; i<N-K; i++) {
        answer += v[i];
    }
    cout << answer << '\n';
} 

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
}