[BOJ 2170] 선 긋기

2170번: 선 긋기

 

1️⃣ 문제 설명

 

2️⃣ 예제 설명

예제 1에서 1~5 구간에서는 겹치는 선이 하나로 인식되어 길이가 4인 선분이 되고, 6~7 구간이 길이가 1인 선분이 되어 그은 선의 총 길이는 4+1=5가 된다.

 

3️⃣ 구현 아이디어 - 틀렸습니다

처음에 문제를 봤을 때 최근에 풀었던 회의실 배정과 비슷해보여 끝나는 지점을 기준으로 정렬하여 문제를 풀어보려고 했다.

N의 최댓값이 1,000,000이고 x와 y의 최솟값과 최댓값이 -1,000,000,000과 1,000,000,000로 매우 큰 수이기 때문에 우선순위 큐를 활용하였다.

💡 로직
1. 두 점의 위치 x, y를 우선순위 큐에 삽입한다. (끝 점을 기준으로 정렬되도록 y를 첫 번째 좌표로)
2. 우선순위 큐의 top을 pop하고, 기준 좌표로 잡는다.
3. 만약 기준 좌표의 끝보다 top의 시작이 작거나 같다면, 기준 좌표의 끝을 top의 끝으로 갱신한다
4. 기준 좌표의 끝이 top의 시작보다 작으면, 기준 좌표를 top으로 갱신한다.
5. 4번이 실행되는 단계에서는 새로운 선을 만난 것이기 때문에 ret에 이제까지 구한 선분의 길이(끝-시작)를 더한다.
6. 마지막 선분의 길이를 더한다.
7. 3~6단계를 우선순위 큐가 빌 때까지 반복한다

 

처음에는 6번을 빼고 구현하였는데, 그럴 경우 마지막 선분의 길이가 고려되지 않기 때문에 추가하였다.

오름차순 정렬을 위해 -를 붙여 삽입해야 하므로 꺼낼 때 다시 -를 붙이는 것을 주의해야 한다!

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int x, y;
priority_queue<pair<int, int>> pq;

int cx, cy;
ll ret;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x >> y;
        // 끝 점 기준 정렬
        // 오름차순을 위해 음수로 삽입
        pq.push({-y, x});
    }

    cx = pq.top().second; // 시작
    cy = -pq.top().first; // 끝
    pq.pop();
    while (!pq.empty()) {
        if (cy >= pq.top().second) { // 기준 좌표의 끝보다 top의 시작이 작거나 같다면
            cy = -pq.top().first;
            pq.pop();
        }
        else { // 기준 좌표의 끝이 top의 시작보다 작으면
            ret += (cy - cx);
            cx = pq.top().second;
            cy = -pq.top().first;
        }
    }
    ret += (cy - cx); // 마지막 선분의 길이

    cout << ret << "\n";

    return 0;
}

 

 

4️⃣ 구현 아이디어 2

질문 게시판에서 반례를 찾을 수 있었다.

3
1 4
2 3
2 6

 

위와 같은 입력일 때, 선분은 1~6 구간으로 총 길이가 5가 되어야 한다.

하지만, cx가 2부터 시작하기 때문에 결과가 4로 나온다.

 

다시 고민해보니, '회의실 배정과 다른 문제인데 꼭 끝 점 기준으로 정렬해줄 필요가 있을까?'라는 생각이 들어 시작점을 기준으로 정렬해주어 코드를 수정하여 해결할 수 있었다!

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int x, y;
priority_queue<pair<int, int>> pq;

int cx, cy;
ll ret;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x >> y;
        // 오름차순을 위해 음수로 삽입
        pq.push({-x, y});
    }

    cx = -pq.top().first; // 시작
    cy = pq.top().second; // 끝
    pq.pop();
    while (!pq.empty()) {
        if (cy >= -pq.top().first) {
            cy = max(cy, pq.top().second);
        }
        else {
            ret += (cy - cx);
            cx = -pq.top().first;
            cy = pq.top().second;
        }
        pq.pop();
    }
    ret += (cy - cx);

    cout << ret << "\n";

    return 0;
}

 

굿