BOJ 백준 15553번 난로

 

 

BOJ 백준 15553 난로

 

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

 

구사과의 방에는 N명의 친구가 오고, 구사과는 친구가 왔을 때 항상 방에 있는 난로를 켠다. 구사과의 방에는 구사과를 포함하여 최대 두 명만 들어올 수 있고, i 번째로 방문하는 친구는 T[i]에서 T[i] + 1 시간에만 방에 있다.  난로를 켤 성냥은 K개만 주어지는데, 난로를 한 번 켤 때 하나의 성냥이 필요하다. 이때 난로가 켜져 있는 시간의 최솟값을 구해야 한다.

 

 

 

우선 예제 입력을 사용하여 어떻게 문제 풀이를 최적화할 수 있을지 고민해 봤다. 다음과 같은 상태라고 가정하자.

 

N = 10,  K = 5, T[i] = {1, 2, 5, 6, 8, 11, 13, 15, 16, 20}

 

 

x축을 방문하는 시간으로 설정하여 친구의 방문시간을 도식화했을 때 어떻게 나타나는지 살펴봤다. 

 

 

 

우선 그림을 이해하기 전에 생각해 보면 최소한 방문하는 친구의 수만큼은 난로를 켜 놔야 한다. 한 명의 친구가 방문할 때마다 1초의 시간을 방에서 지내고, 그 시간 동안은 반드시 난로를 켜야 한다고 문제에서 전제하였기 때문이다. 그리고 친구들이 방문하는 시간 구간 사이에 간격이 존재하지 않을 수도 있다. 위의 그림에서처럼 1초에 첫 번째 친구가 와서 2초까지 방에 있고, 2초에 두 번째 친구가 와서 3초까지 방에 있다가 나간다. 이처럼 방문 시간 구간 사이에 간격이 없으면 난로를 무조건 연속해서 틀어 놔야 한다. 성냥을 최소한으로 사용해서 나중에 성냥을 켤 일이 있을 때를 대비해야 해서다. 그러므로 방문 시간이 연속으로 오는 구간은 하나의 구간으로 봐야 한다.

 

 

 

그런데 총 구간의 개수보다 성냥의 개수가 부족하면 일부 구간 사이의 간격을 채워야 한다. 간격의 수만큼 성냥으로 난로를 켤 수 있기 때문이다. 따라서 간격의 크기를 최소한으로 하여 총구간의 개수를 성냥의 개수만큼만 되도록 만들어야 한다. 예제 입력에서는 연속된 구간을 하나의 구간으로 고려할 때 총구간의 개수는 7개인데 반해 성냥은 5개이므로, 구간 사이 간격을 채워서 총구간의 수를 5개로 만들어야 한다. 위의 그림에서 보면 가장 작은 구간 사이 간격은 크기가 1인 간격 2개다. 따라서 방문하는 친구 수 10에 2를 더하면 난로를 켜는 최소 시간이 된다.

 

 

 

따라서 이 문제는 탐욕 알고리즘(Greedy Algorithm)으로 해결 가능하다. 일반화한 식은 위의 노트를 참고하면 된다.

 

 

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    
    vector<int> t(n), interval;
    
    for (int i = 0; i < n; i++){
        scanf("%d", &t[i]);
    }
    
    int section_start = t[0], section_end = t[0] + 1;
    int cnt = 1;
    
    for (int i = 1; i < n; i++){
        // 새로 시작하는 친구 방문 구간이면
        if (section_end != t[i]){
            cnt += 1;
            interval.push_back(t[i] - section_end);
            section_start = t[i];
            section_end = t[i] + 1;
        }
        // 이전 친구 구간에 이어서 오는 경우
        else {
            section_end = t[i] + 1;
        }
    }
    
    sort(interval.begin(), interval.end());
    
    if (k < cnt){
        int sum = n;
        for (int i = 0; i < cnt - k; i++){
            sum += interval[i];
        }
        printf("%d\n", sum);
    }
    else {
        printf("%d\n", n);
    }
    
    return 0;
}