H. Lifeguards (Bronze)

Editor: 김정현 (powergee)

문제 상황 설명

N마리의 소가 인명 구조원으로 활동하고 있습니다.N마리의 소가 각자 담당하고 있는 시간이 있는데, 자금의 문제로 한 마리만 해고해야 합니다. 최소 한마리의 인명 구조원이 활동하는 시간이 최대가 되도록 적절히 한 마리를 해고하고자 합니다. 그렇다면 한 마리를 해고한 뒤에 최소 한 마리의 인명 구조원이 활동하는 최대 시간은 얼마일까요?

문제 풀이

이 문제에 대하여 생각할 수 있는 가장 간단한 풀이는 N마리의 모든 소들을 각각 해고하는 모든 경우를 계산하고 한 마리 이상이 활동하는 시간이 최대가 되는 경우를 찾는 것입니다. 다시말해, 1번째 소를 해고하는 경우의 시간, 2번째 소를 해고하는 경우의 시간, ..., N번째 소를 해고하는 경우의 시간을 모두 계산해봄으로써 최대 시간을 가지는 경우를 찾아낼 수 있습니다.

한 마리의 소를 제외한 소들의 집합에 대하여 최소 한 마리의 인명 구조원이 활동하는 총 시간을 계산하는 방법을 생각해야 합니다. 한 마리의 소를 제외한 소들의 집합을 $S$라고 하고, 그 집합의 $i$번째 소가 담당하는 시간을 구간 $[t_{i, start}, t_{i, end}]$라고 하겠습니다. 총 시간을 계산하는데 아래와 같은 과정을 이용할 수 있습니다.

아래 과정을 따르기 전에 각 소들이 담당하는 시간 구간을 담은 배열을 구간의 시작점을 기준으로 정렬해야 합니다. 여기서 시작점이 같은 두 개이상의 구간에 대해서는 끝점을 기준으로 오름차순 정렬합니다.

1. 시간 구간을 표현하는 변수 $c$를 선언하고, 이것의 초기값을 $[-1, -1]$ 로 합니다. 이 구간의 시작점과 끝점은 각각 $t_{c, start}$, $t_{c, end}$ 로 명명하겠습니다.

2. 총 시간을 표현하는 정수형 변수 $T$를 선언하고, 이것의 초기값을 0으로 합니다.

3. $S$ 의 모든 $i$ 번째 소에 대하여 순서대로 아래 분기를 수행합니다.

   1. 만약 $t_{c, end} <t_{i, start}$ 라면, $c$에 $[t_{c, start}, t_{c, end}]$ 를 대입하고 $T$에 $(t_{c, end}-t_{c, start})$를 더합니다.

   2. 만약 $t_{c, end}\geq t_{c, start}$ 라면, $c$의 $t_{c, end}$에 $t_{i, end}$를 대입하고 $T$에 $(t_{i, end}-t_{c, end})$를 더합니다.

4. 3번 과정을 수행한 뒤의 $T$가 총 시간이 됩니다.

N마리의 모든 소에 대하여 반복문을 실행하는 데 $O(n)$ 의 시간 복잡도가 소요되며, 한 마리를 제외했을 때 최소 한마리의 인명 구조원이 활동하는 시간을 계산하는 데 $O(n)$ 의 시간 복잡도가 소요됩니다. 따라서 알고리즘 전체의 시간 복잡도는 $O(n^2)$ 입니다. (N개의 입력을 받는데 $O(n)$, 입력을 정렬하는 데 $O(n\log n)$이지만 가장 큰 $O(n^2)$만 생각하였습니다.)

이 문제에서 N의 범위는 $1\leq N\leq 100$ 에 불과하므로, $O(n^2)$의 큰 시간 복잡도로도 시간 제한 안에 결과를 도출할 수 있습니다.

이 문제의 제목에서 유추할 수 있듯이, 이 문제는 Bronze, Silver, Platinum의 3가지 난이도가 존재합니다. 이 풀이는 주어진 문제 상황에서 이용할 수 있는 여러가지 방법들 중 하나이며, 상대적으로 큰 시간 복잡도를 가지고 있습니다. Silver와 Platinum 난이도에서는 입력 데이터의 범위가 매우 크기 때문에 이 풀이 방법으로는 시간 내에 해결할 수 없습니다. 이들을 해결하기 위해서 라인 스위핑(Line Sweeping)과 같은 알고리즘 기법을 이용할 수 있습니다. 기회가 된다면 Silver, Platinum의 심화 버전 또한 도전해보시길 바랍니다.

소스 코드 (C++)

Lifeguards (Bronze).cpp

#include <iostream>
#include <algorithm>

typedef std::pair<int, int> Range;

int N;
Range shifts[100];

int CalcTime(int ignore)
{
    Range curr = {-1, -1};
    int time = 0;

    for (int i = 0; i < N; ++i)
    {
        if (i == ignore)
            continue;

        if (curr.second < shifts[i].first)
        {
            curr = shifts[i];
            time += shifts[i].second - shifts[i].first;
        }
        else
        {
            time += shifts[i].second - curr.second;
            curr.second = shifts[i].second;
        }
    }

    return time;
}

int main()
{
    scanf("%d", &N);

    for (int i = 0; i < N; ++i)
        scanf("%d %d", &shifts[i].first, &shifts[i].second);

    std::sort(shifts, shifts + N);

    int maxTime = -1;
    for (int i = 0; i < N; ++i)
        maxTime = std::max(maxTime, CalcTime(i));

    printf("%d", maxTime);

    return 0;
}