[BOJ 1905] 상자 쌓기

체감 난이도: Gold V + 2.6

 

태그

• Imperfect Time Complexity (시간복잡도 상으로 느린 풀이가 통과됨)
• Tree Set

 

풀이

1. 특정 상자가 놓이는 위치는?

지금 놓아야 할 상자의 위치가 \( [x_1, x_2] \times [y_1, y_2] \)라고 합시다.

 

그럼, 이전에 놓인 상자들 중 위 직사각형과 겹치는 상자들만 볼 때, 이 중 가장 높은 곳에 놓인 상자 위에 놓이게 됩니다.

 

2. 이거 시간 복잡도 괜찮나?

새로운 상자를 볼 때마다, 이전 상자들을 하나씩 다 둘러보는 방식을 생각해봅시다.

 

대충 생각해봐도 \( O(N^2) \)입니다. 심지어 \( O(N^2) \)인 데이터도 간단히 만들 수 있습니다.

 

하지만 \( N \le 20\,000 \)이고 3초 시간 제한이면, \( N^2 = 400\,000\,000 \) 정도가 돌아도 할 말은 없죠.

 

코드

지금까지 본 상자들을 multiset에 담가두고, 높이가 높은 상자부터 보도록 코드를 짰습니다.

bool cmp(pi5 a, pi5 b){ return a.sc > b.sc; }
multiset<pi5, decltype(&cmp)> s(cmp);
 
void Main(){
    int x, y, n; cin >> x >> y >> n;
    s.insert({ { {0, 0}, {y, x} }, 0 });
    for (int i = 1; i <= n; i++){
        int dx, dy, dz, x, y; cin >> dx >> dy >> dz >> x >> y;
        int x1 = x, x2 = x+dx-1, y1 = y, y2 = y+dy-1;
        for (pi5 p : s){
            int y3 = p.fr.fr.fr, y4 = p.fr.sc.fr;
            int x3 = p.fr.fr.sc, x4 = p.fr.sc.sc;
            int z3 = p.sc;
            if (!(y4 < y1 || y2 < y3) && !(x4 < x1 || x2 < x3)){
                //cout << y1 << ' ' << y2 << "   " << x1 << ' ' << x2 << "   " << z3+dz << endl;
                s.insert({ { {y1, x1}, {y2, x2} }, z3+dz });
                break;
            }
        }
    }
    cout << (*(s.begin())).sc;
}