[백준/BOJ] 2532 먹이사슬 (c++)

[백준/BOJ] 2532 먹이사슬 (c++)

2532번: 먹이사슬

2025.03.04 - [Competitive Programming] - 14. Longest Increasing Subsequence (LIS, c++)

14. Longest Increasing Subsequence (LIS, c++)

---

N마리의 동물이 있고 동물들의 활동 영역이 주어집니다.

 

만약 A라는 동물의 활동영역에  B라는 동물의 활동영역이 포함된다면 A는 B보다 먹이사슬에서 상위에 있다고 합니다.

 

이 때 존재하는 먹이사슬 구조 중 가장 큰 먹이사슬 구조의 크기를 구해야 합니다.

 

우선 구간의 시작과 끝 중 한쪽 조건을 고정시키기 위해 시작 구간을 기준으로 오름차순 정렬을 합니다. 

 

이제 시작 구간 오름차순으로 정렬된 배열을 순차적으로 탐색한다면 종료 구간이 감소하는 형태인 경우 앞에 있는 동물보다 먹이사슬 아래에 있다고 말할 수 있습니다.

 

뒤에 나온 값이 앞에 나온 값보다 작다면 시작구간도 늦고 종료구간도 빠른 것이기 때문입니다.

 

시작구간이 같은 경우에는 종료구간이 작은 동물이 먹이사슬에 포함되므로 내림차순으로 정렬을 해줍니다.

 

예를 들어 문제의 예시를 정렬하게 되면 [1, 5], [2, 4], [3, 4], [5, 7] .... 와 같은 형태가 될텐데

 

5 -> 4 의 경우 감소하는 형태이기 때문에 먹이사슬에 있는 것이고 4 -> 7의 경우 증가하는 형태이므로 먹이사슬이 아니게 됩니다.

 

그러므로 정렬된 배열에 대해 종료구간에서의 가장 긴 감소하는 부분수열(LDS)를 O(NlogN)에 구하면 N이 50만이므로 이 문제가 풀리게 됩니다.

 

LDS는 LIS를 구하는 것과 동일하지만 dp 배열에 저장하는 값을 부호를 변경해서 저장해주면 됩니다.

 

또한 5->4->4와 같이 같은 값이 나오더라도 먹이사슬에 있는 것으로 계산해야하기 때문에 LIS를 구하는 과정에서 lower_bound 대신 upper_bound를 구한다면 같은 값을 포함하는 부분수열을 구할 수 있습니다.

---

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
int N;
vector<pair<int, int>> a;

bool compare(const pair<int, int>& a, const pair<int, int>& b) {
    if (a.first == b.first) return a.second > b.second;
    return a.first < b.first;
}
int solve() {
    sort(a.begin(), a.end(), compare);
    a.erase(unique(a.begin(), a.end()), a.end());
    vector<int> d;
    REP(i, 0, (int)a.size()) {
        int index = upper_bound(d.begin(), d.end(), -a[i].second)-d.begin();
        if (index >= (int)d.size()) d.push_back(-a[i].second);
        else d[index] = -a[i].second;
    }
    cout << d.size();
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    int n, s, e;
    REP(i, 0, N) {
        cin >> n >> s >> e;
        a.push_back({s, e});
    }
    solve();
    return 0;
}