boj 15553 난로

https://www.acmicpc.net/problem/15553

 

N명의 친구가 방에 방문할 예정이고, 친구가 있는 시간에는 난로가 켜져 있어야 합니다.

난로는 K번까지 켤 수 있으며, 난로가 켜져있는 최소 시간을 구해야합니다.

 

이 문제는 인접한 시간의 간격을 이용하여 그리디하게 문제를 풀 수 있습니다.

우선 N명의 친구가 방문할때는 난로가 켜져있어야 하기 때문에 N번의 난로를 모두 켜주도록 합니다.

여기서 난로가 켜져있는 시간은 N이고, N번 난로를 켠 상태입니다.

 

난로는 최대 K번까지만 켤 수 있으므로 "친구가 나간 시간 ~ 다른 친구가 들어온 시간"의 간격 동안에는 난로가 추가로 켜져있어야 합니다.

즉 list[i] - (list[i - 1] + 1) 시간 동안에는 추가로 난로가 켜져 있어야 합니다.

그렇다면 이 시간들을 작은 값부터 더해준다면 답을 구할 수 있습니다.

 

저는 그 시간들을 벡터에 넣어줬고, 벡터를 오름차순으로 정렬했습니다.

이후에는 cnt = K가 될때까지 벡터에 있는 시간들을 추가로 더해주도록 합니다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100001
using namespace std;
 
vector<int> v;
int list[MAX];
int N, K;
 
void func() {
    for (int i = 1; i < N; i++) {
        v.push_back(list[i] - (list[i - 1] + 1));
    }
    sort(v.begin(), v.end());
 
    int ret = N;
    int cnt = N;
    int idx = 0;
    while (cnt > K) {
        ret += v[idx++];
        cnt--;
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}