백준 2532번 : 먹이사슬 풀이

1. 문제 링크

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

 

---

2. 풀이 방법

각 동물의 번호, 동물의 활동영역의 왼쪽 위치, 오른쪽 위치가 입력으로 들어온다.

이 중에서 번호는 필요하지 않으므로, 왼쪽 위치와 오른쪽 위치를 묶어서 저장해주었다.

// 헤더
using pii = pair<int, int>;

// main 함수
vector<pii> animals;

for (int i = 0; i < n; i++) {
    int idx, l, r;
    cin >> idx >> l >> r;

    animals.emplace_back(l, r);
}

 

우선 활동영역을 정렬했는데, 왼쪽 위치에 대해 내림차순이 되도록, 왼쪽 위치가 같은 경우에는 오른쪽 위치에 대해 오름차순이 되도록 정렬했다.

struct cmp{
    bool operator()(const pii &a, const pii &b) const {
        if (a.first != b.first) {
            return a.first > b.first;
        }

        return a.second < b.second;
    }
};

sort(animals.begin(), animals.end(), cmp());

 

이후 오른쪽 위치에 대해 LIS를 적용하여 풀었다.

 

그런데 먹이사슬 조건에 따르면, (3, 4) 와 (2, 4) 같은 경우에도 먹이사슬 조건을 만족하게 되므로 일반적인 LIS와는 달리 같은 값이 여러 번 등장해도 된다. 다시 말해서, 일반적인 LIS는 strictly increasing인 가장 긴 수열을 구하는 반면, 여기서는 non-decreasing 조건을 만족하는 가장 긴 수열을 구하면 된다. 따라서 LIS를 구하는 과정에서 기존의 lower_bound 대신 upper_bound 를 대신 사용했다.

 

(쉽게 설명하면 lower_bound 를 이용하여 a 이상인 자리 중 가장 작은 자리를 찾은 후 그 자리에 a를 넣으면 선택한 수열에 a가 단 한 개만 존재할 수 있지만, a 초과인 자리 중 가장 작은 자리를 찾아서 a를 넣으면 선택한 수열에 a가 여러 개 존재할 수 있게 되므로 upper_bound 를 사용하는 것)

 

또한 완전히 일치하는 활동영역이 여러 번 중복해서 들어오는 입력도 있을 수 있기 때문에, 정렬된 활동영역 목록을 순회하면서 이전 활동영역과 완전히 일치할 경우에는 건너뛰도록 했다.

vector<int> memo;

for (int i = 0; i < n; i++) {
    // 이전 활동영역과 완전히 일치하는 경우에는 skip한다.
    if (i >= 1 && animals[i - 1] == animals[i]) {
        continue;
    }

    // 선택한 수열에 같은 값이 여러 번 등장해도 되므로 lower_bound 대신 upper_bound를 사용한다.
    auto it = upper_bound(memo.begin(), memo.end(), animals[i].second);

    if (it == memo.end()) {
        memo.push_back(animals[i].second);
    }
    else {
        *it = animals[i].second;
    }
}

 

---

3. 전체 코드 (C++)

• C++ : https://github.com/infikei/algorithm/blob/main/baekjoon_all/02000%2B/boj_2532.cpp