BOJ 1202 보석도둑

매트로이드(matroid) 구조를 가진 그리디 문제입니다

보석은 비싼순서대로 가방은 가벼운 순서대로 정렬해두고, 가장 비싼 보석부터 담을 수 있는 가능한 작은 가방에 담아주면 해결 할 수 있습니다

다만 이때 $N$의 크기가 30만이라 $O\left ( N^2 \right )$으로는 TLE를 받습니다

따라서 N한개에 뒤에는 로그가 따라오는 정도로 문제를 풀어야합니다

저는 $O\left ( Nlog N \right )$안에 해결했습니다

하지만 이 부분에서 가방을 그냥 벡터에 넣고 lower_bound를 쓰면 TLE를 맞습니다(벡터을 이용한 구현)

가방을 multi_set에 넣고 bag.lower_bound를 사용해야 시간안에 동작합니다(set을 통한 구현)

set이 random-access iterator를 지원하지 않다는 점에서 set자체의 lower_bound를 호출해야 한다는 점은 이해가 잘 됩니다

그런데 vector는 random-access iterator를 지원하는데 TLE가 나오는 점은 이해되지 않습니다

 

공식문서에 나온 std::lower_bound 사용법을 읽어 보아도 LegacyRandomAccessIterator 를 제공하는 자료구조에 대해서는 logarithmic하게 동작한다고 하는데, vector의 공식문서에서는 이를 제공한다고 나와있기 때문입니다

그러니 벡터를 사용해도 같은 로그시간안에 동작해야하지만 그렇지 않아 의아한 점이 생길 수 있습니다

 

이 부분에 대한 차이는 바로 사용한 가방을 삭제하는 연산에서 발생합니다

벡터의 경우 앞,뒤 원소의 삭제에 대해서는 상수시간안에 동작하지만 그 외의 원소에 대해서는 선형시간으로 동작합니다

하지만 set의 경우 비교, 검색, 삽입, 삭제 모두 로그시간안에 동작하기 때문입니다

따라서 사용할 가방을 찾는 연산에 대해서는 올바른 시간안에 동작하지만, 가방을 삭제할때는 선형시간으로 동작하기 때문에 벡터를 이용하면 TLE를 맞게됩니다

for (ll i = n-1; i >=0 ; i--) {
        ll w = dia[i].Y;
        auto it = bag.lower_bound(w);
        if (it!=bag.end()) {
            ans+=dia[i].X;
            bag.erase(it);
        }
    }

문제보다 중요한건 매트로이드 구조입니다

하지만 저는 매트로이드의 상속성에 대해서는 이해를 하고 있지만, 교환성은 이해가 가질 않았습니다

 

$A,B\in I$이고$\left | A \right | < \left | B \right |$ 이면 $A \cup \left \{ x \right \} \in  I$인 $x\in B-A$가 존재한다

 

위 부분이 이해가지 않아서 아예 책을 구매했습니다

"쉽게 배우는 알고리즘"이라는 책인데 내용이 정말 좋은 것 같습니다

 

많이 부족해서 그런지 공부를 할 수록 배울게 늘어납니다

하지만 이런게 나쁘지만은 않은 것 같습니다 (๑╹∀╹๑)