백준 2024번: 선분 덮기

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

2024번: 선분 덮기

문제 설명만 보면 단순한 라인 스위핑 문제로 착각하기 쉽지만, 사실 이 문제는 일반적인 라인 스위핑처럼 모든 선을 사용하는 문제가 아니다. 예를 들어 두 선 [3, 5]와 [3, 8] 중 한 가지 선분을 사용할 경우 선 [3, 8]을 사용하는 것이 반드시 이득이다.

A < P < B일 때, 구간 [0, A]에서 시작하는 선들을 이용해 구간 [0, B]를 덮었고 구간 [P, Q]를 덮는 선 pq를 구간에 추가하고자 한다고 가정하자. 이 때 Q < B라면, 즉 선 pq가 지점 B 이전에 끝난다면 선 pq를 사용할 필요가 없고, 구간 [0, B]를 덮은 선 중 구간 [0, Q]에 속하는 선 pq'가 있다면 선 pq를 사용해 구간 [0, Q]를 덮은 이후 선 pq'를 사용할 필요가 없으므로 선 pq'를 제거한다. 이 과정을 구간 [0, M]을 덮을 때까지 반복하면 구간 [0, M]을 덮는 최소 선의 개수를 구할 수 있다.

#include <iostream>

using namespace std;

#define MAX_M 50000

int max(int a, int b) { return a > b ? a : b; }
int relu(int num) { return max(num, 0); }

int main() {
    // M: 덮을 구간의 길이, l, r: 각 선의 좌우 좌표, ans: 최소 선의 개수
    int M, l, r, ans = 0;
    // line[i]: i에서 시작하는 선 중 가장 긴 선의 오른쪽 좌표
    // arr[i]: 구간 [0, M]을 덮는 선분 중 i번째 선분의 오른쪽 좌표
    int line[MAX_M + 1] = { 0, }, arr[MAX_M + 1] = { 0, };

    // 덮을 구간의 길이를 입력받은 뒤
    cin >> M;
    do {
        // 각 선의 좌우 좌표를 입력받고
        cin >> l >> r;
        // 왼쪽 좌표를 기준으로 가장 긴 선의 오른쪽 좌표를 갱신
        line[relu(l)] = max(line[relu(l)], relu(r));
    // 입력이 끝날 때까지, 즉 "0 0"을 입력받을 때까지 반복
    } while (l || r);

    // 0번 좌표를 지나는 선이 존재한다면
    if (line[0]) {
        // 해당 선을 구간을 덮는 첫번째 선으로 지정
        arr[ans++] = line[0];

        // 왼쪽 좌표가 1부터 덮은 구간의 각 좌표에 대해
        for (int i = 1; i <= arr[ans - 1] && arr[ans - 1] < M; i++)
            // 해당 좌표에서 시작하는 선이 덮은 구간을 넘어설 때
            if (line[i] > arr[ans - 1]) {
                // 덮은 구간을 이루는 선 중 현재 선과 겹치는 선이 있다면 제거
                while (ans >= 2 && i <= arr[ans - 2]) ans--;
                // 현재 선을 구간을 덮을 선의 집합에 추가
                arr[ans++] = line[i];
            }
    }

    // 구간을 덮는 선의 집합 중 마지막 선의 오른쪽 좌표가 M 미만이라면 구간을 덮지 못함
    // 따라서 마지막 선이 좌표 M을 포함하는지에 따라 ans 혹은 0울 반환
    cout << ans * (arr[ans - 1] >= M) << '\n';

    return 0;
}