백준 15553 - 난로

문제 설명

구사과의 방에는 난로가 하나 있다. 구사과는 절약 정신이 투철하기 때문에, 방에 혼자 있을 때는 난로를 되도록 켜지 않는다. 구사과는 방에 친구가 왔을 때는 항상 난로를 켠다.

오늘은 N명의 친구들이 구사과의 집에 방문하는 날이다. 구사과는 친구들을 쉽게 구분하기 위해 1부터 N까지 번호를 매겼다. i번째 친구는 구사과의 방에 시간 Ti에 도착하고, 시간 Ti+1에 나간다. 구사과의 방은 좁기 때문에, 한 번에 한 명만 방문할 수 있다. 즉, 방안에는 항상 구사과를 포함해 2명 이하의 사람만 있게 된다.

구사과는 난로를 아무 때나 켤 수 있고, 끌 수 있다. 난로를 켜려면 성냥을 이용해야 한다. 오늘 구사과는 총 K개의 성냥을 가지고 있다. 따라서, 최대 K번 난로를 켤 수 있다. 가장 처음에 난로는 꺼져있다.

구사과는 난로가 켜져 있는 시간을 최소로 하려고 한다. 구사과의 친구들이 도착하는 시간과 가지고 있는 성냥의 개수가 주어졌을 때, 난로가 켜져 있는 시간의 최솟값을 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N명의 친구가 집을 방문할 때 난로를 켜야 한다.

단, K개의 성냥으로만 불을 켤 수 있기 때문에 난로를 끄지 못하는 경우도 존재한다.

난로를 켜는 시간의 최솟값을 구해야 한다.

 

해당 문제는 조금만 다르게 생각하면 간단하게 풀 수 있다.

우선, 성냥의 개수에 집중해 보자.

성냥이 K개이기 때문에 난로가 켜져 있는 구간은 K개의 구간이 된다.

난로가 켜져 있는 시간이 최소가 되려면 각 구간의 길이가 최소가 되어야 한다.

이를 다르게 생각해 보면, 구간의 길이가 최소가 되게 하는 것은 구간끼리의 거리가 최대가 되는 것과 같다.

즉, K개의 구간 사이의 K-1개의 간격이 최대가 되면 K개의 구간의 길이의 합은 최소가 된다.

 

구간사이의 간격을 구하는 법은 간단하다.

모든 친구의 방문 사이의 간격을 계산한 후, 정렬하면 된다.

int start = INT_MAX, end = 0;
for (int i = 0; i < N; i++)
{
    cin >> friends[i];
    start = min(start, friends[i]);
    end = max(end, friends[i]);
}

int ans = end - start + 1;
vector<tuple<int, int, int>> gaps;
for (int i = 1; i < N; i++)
{
    int gap = friends[i] - friends[i - 1] - 1;
    gaps.push_back({ gap, i - 1, i });
}

sort(gaps.begin(), gaps.end(), greater());

 

이제 K개의 구간을 나누었으니 난로가 켜져 있던 시간을 구하면 된다.

난로는 시작부터 끝까지의 시간 중 K-1개의 간격을 제외하고는 항상 켜져있어야 한다.

따라서, 끝-시작+1로 전체 시간을 구한 뒤, K-1개의 간격을 큰 것부터 빼면 된다.

for (int i = 0; i < K-1; i++)
{
    auto [gap, currentStart, curresntEnd] = gaps[i];
    ans -= gap;
}

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N, K;
vector<int> friends;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);

    cin >> N >> K;
    friends.resize(N);

    int start = INT_MAX, end = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> friends[i];
        start = min(start, friends[i]);
        end = max(end, friends[i]);
    }

    int ans = end - start + 1;
    vector<tuple<int, int, int>> gaps;
    for (int i = 1; i < N; i++)
    {
        int gap = friends[i] - friends[i - 1] - 1;
        gaps.push_back({ gap, i - 1, i });
    }

    sort(gaps.begin(), gaps.end(), greater());

    for (int i = 0; i < K-1; i++)
    {
        auto [gap, currentStart, curresntEnd] = gaps[i];
        ans -= gap;
    }

    cout << ans;

    return 0;
}

---