백준 24229번 모두싸인 출근길

문제 링크

간단한 DP문제. 판자를 입력받고, 정렬하고, 겹치는 판자끼리 이어붙인다. 이 때 실수하지 않도록 주의. 마지막 판자의 종료 지점보다 새로운 판자의 시작 지점이 앞선다면 판자가 겹치는 것이다. 판자가 겹친다면 판자의 종료 지점을 두 판자 중 더 멀리 있는 판자의 종료 지점으로 설정해야 한다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

int N, cache[200000];
vector<pair<int, int>> v;

int solve(int cur) {
    int& ret = cache[cur];
    if (ret != -1) return ret;
    ret = v[cur].second;
    
    int i = 0, cnt = v[cur].second - v[cur].first;
    while (++i) {
        if (cur + i >= v.size() || v[cur + i].first > v[cur].second + cnt) break;
        ret = max(ret, solve(cur + i));
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    vector<pair<int, int>> tmp(N);
    for (auto& [a, b] : tmp) {
        cin >> a >> b;
    }

    sort(tmp.begin(), tmp.end());

    for (int i = 0; i < N; i++) {
        if (v.size() && v[v.size()-1].second >= tmp[i].first) {
            v[v.size()-1].second = max(v[v.size()-1].second, tmp[i].second);
        }
        else v.emplace_back(tmp[i]);
    }

    memset(cache, -1, sizeof(cache));
    cout << solve(0);

    return 0;
}