[백준] 2532: 먹이사슬

0. 문제 주소

 

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

2532번: 먹이사슬

 

 

1. 풀이

 

 

 

LIS 응용 문제. 원소간 크기 비교의 정의가 기존과 다르기 때문에 새로 정의해주어야 한다.

 

조건 1: x1 < x3 이고  x2 > x4

조건 2: x1 = x3 이고 x2 > x4  

조건 3: x1 < x3 이고 x2 = x4 

 

라는 조건에서, 선분 두 개의 양 끝이 서로 같을 경우, 서로는 먹이사슬 구조를 이루지 않는 점을 주의해야 한다.

 

따라서 주어진 input 들 중 양 끝이 같은 원소들을, 즉 중복된 원소들을 미리 제거해주어야 하는데,

 

선분들을 먼저 정렬해준 다음 제거해야 한다.

 

vector 내 중복된 원소의 제거를 위해 vector.erase(unique(vector.begin(), vector.end()), vector.end())를 사용해야 하는데

 

unique는 vector 내의 연속된 중복 원소들을 맨 끝으로 보내주기 때문에, 미리 정렬을 해준 뒤 사용해야 한다. 처음 알았다.

 

선분들을 왼쪽 끝을 오름차순으로, 왼쪽 끝이 같다면 오른쪽 끝은 내림차순으로 정렬해주어야 포함 관계로 정의된 크기 비교가 원활해진다.

 

이렇게 정렬을 해주고 나면, 왼쪽 끝은 이미 전체가 IS 형태를 갖고 있으므로, LDS의 최대 길이를 찾아주면 된다.

 

LIS 역추적 포스팅을 아직 안 해서 간단하게 적어보면,

 

[PS/DP] - [BOJ] 2352: 반도체 설계에서 든 예시를 이어서 설명하겠다.

 

4 2 6 3 1 5 에서 lower_bound를 이용하여 LIS 벡터를 채워나가는데, i번째 원소가 LIS 벡터에 삽입되는 index를 pos[i]에 저장해둔다. 

 

다음, t = LIS.size - 1로 초기화해두고, i=N-1부터 0까지 pos[i] == t일 땐 '실제 LIS의 t번째 원소는 num[i]'라고 사용하면 된다.

 

예시로는 pos 배열이 0 0 1 1 0 2 로 나오게 되고, LIS의 크기는 3이 된다.

 

t = 2부터 시작하여, pos 배열을 역으로 탐색하면 index가 5, 3, 1인 원소가 각각 LIS의 2, 1, 0번째 원소가 된다고 이해할 수 있다.

 

즉 num = 4 2 6 3 1 5에서, LIS = 2 (=num[1]) , 3 (=num[3]) , 5 (=num[5]) 로 구할 수 있다는 뜻이다.

 

 

 

 

2. 풀이 코드

 

* 유의할 점

 

#include <iostream>
#include <vector>
#include <algorithm>

#define pii pair<int, int>
#define MAX 500005

using namespace std;

int N;
vector<pii> ani;
vector<int> LIS;

bool cmp(const pii A, const pii B){
    if (A.first == B.first) return A.second > B.second;
    return A.first < B.first;
}

bool lb_comp(const int a, const int b){
    return a >= b;
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d", &N);
    int num, a, b;
    for (int i=0;i<N;i++){
        scanf("%d %d %d", &num, &a, &b);
        ani.push_back(pii(a, b));
    }
    
    sort(ani.begin(), ani.end(), cmp);
    ani.erase(unique(ani.begin(), ani.end()), ani.end());
    LIS.push_back(ani[0].second);
    for (int i=1;i<N;i++){
        int curr = ani[i].second;
        auto it = lower_bound(LIS.begin(), LIS.end(), curr, lb_comp);
        if (it == LIS.end()) LIS.push_back(curr);
        else *it = curr;
        
    }
    printf("%d\n", LIS.size());
    
    

    return 0;
}