[백준/C++] #24229 모두싸인 출근길 (Greedy)

문제

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

 

구상

문제를 읽고나서 DP나 greedy 종류의 문제인 것 같았다. 이전에 이동한 곳을 벡터든 변수든 큐든 저장을 해놓고 다음 위치로 이동할 수 있는지 없는지 확인 한 후 이동시키는 거였으니까. 문제는 한 장소에서 이동할 수 있는 유효 거리 안에 판자 여러개가 있을 수 있고, 무조건 가까운 판자를 고르거나 먼 판자를 고르는 것이 정답이 아니라는 점이었다. 그래서 우선순위 큐(max heap)를 사용하여 현재 위치(R)에서 이동할 수 있는 모든 판자를 구하면서 큐에 해당 판자의 R을 넣었다. 그렇게 큐에 원소가 없을 때까지 최종 도달 위치를 가장 먼 곳으로 갱신하다 보면 답이 도출된다. 

 

문제 자체는 쉬웠는데 구현이 좀 빡셌다. 자잘자잘한 것들이 참 많았던 것 같다. 화남주의!!

 

그리고 초반에 판자들이 겹칠 수 있다는 점 때문에 계속 구현이 간단명료하게 안 되어서 겹치는 판자들은 하나로 통일해주어 로직 자체를 단순화했다. 

 

풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define endl "\n"
using namespace std;
/*
24229 모두 싸인 출근길
*/

int n; // 판자의 개수 1~200,000
vector<pair<int, int>> wood; // {L, R}
int res = 0;

void merge_wood() {

    // 널판지를 L 기준으로 오름차순 정렬
    sort(wood.begin(), wood.end());

    // 병합된 널판지를 저장할 벡터
    vector<pair<int, int>> merged;

    // 초기 널판지 설정
    int current_L = wood[0].first;
    int current_R = wood[0].second;

    for (int i = 1; i < n; i++) {
        if (wood[i].first <= current_R) {
            // 현재 널판지가 겹치거나 인접하는 경우 병합
            current_R = max(current_R, wood[i].second);
        }
        else {
            // 병합이 끝난 경우, 병합된 널판지를 추가하고 새 널판지로 초기화
            merged.push_back({ current_L, current_R });
            current_L = wood[i].first;
            current_R = wood[i].second;
        }
    }
    // 마지막 병합된 널판지 추가
    merged.push_back({ current_L, current_R });

    // 병합된 결과를 원래 벡터에 덮어씌움
    wood = merged;
    n = wood.size(); // 병합 후 널판지 개수 갱신
}

void solution() {

    priority_queue<pair<int, int>> pq; // 기본이 max heap
    pq.push({ wood[0].second, 0 });

    while (!pq.empty()) {
        int now = pq.top().first; // R
        int now_wood = pq.top().second; // wood_idx
        pq.pop();

        int next = now_wood + 1;
        while (next < n) {
            int jump_distance = wood[now_wood].second - wood[now_wood].first;
            int new_position = wood[now_wood].second + jump_distance; // 갈 수 있는 가장 먼 곳

            // 도달 가능한 곳이라면
            if (new_position >= wood[next].first) {
                pq.push({ wood[next].second, next });
                next++;
            }
            // 도달 불가능한 곳이라면
            else {
                break;
            }
        }

        // 최종 도달 위치 갱신
        res = max(res, now);
    }

    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    wood.resize(n);

    for (int i = 0; i < n; i++) {
        int L, R;
        cin >> L >> R;
        wood[i] = { L, R };
    }

    // 널판지 병합
    merge_wood();

    // 디버깅
    //for (const auto& w : wood) {
    //    cout << "Merged wood: [" << w.first << ", " << w.second << "]" << endl;
    //}

    solution();

    return 0;
}