[Easy] Over9000Rocks
Topcoder SRM 539 Div1
상자가 15개 이하이므로
상자들의 가능한 부분집합을 모두 살펴볼 수 있다.
부분집합에 속하는 상자들의 lower 와 upper 를 모아 더하면
그 부분집합이 만드는 돌 개수의 최소와 최대가 나온다.
부분집합마다 돌 개수의 범위를 구간으로 만들고 정렬해둔다.
앞에서부터 sweep 하면서 구간으로 덮인 좌표의 개수를 세어주면 된다.
9000을 넘는 좌표만 세어야 한다는 것을 주의하자.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <vector> | |
| #include <algorithm> | |
| using namespace std; | |
| class Over9000Rocks { | |
| public: | |
| int countPossibilities(vector<int> lowerBound, vector<int> upperBound) { | |
| vector<pair<int, int>> segs; | |
| int n = lowerBound.size(); | |
| for (int s = 1; s < (1 << n); ++s) { | |
| int mn = 0, mx = 0; | |
| for (int i = 0; i < n; ++i) { | |
| if (s & (1 << i)) { | |
| mn += lowerBound[i]; | |
| mx += upperBound[i]; | |
| } | |
| } | |
| segs.emplace_back(mn, mx); | |
| } | |
| sort(segs.begin(), segs.end()); | |
| int prv = 9000, ans = 0; | |
| for (const auto& seg : segs) { | |
| if (prv < seg.first) { | |
| ans += seg.second - seg.first + 1; | |
| prv = seg.second; | |
| } | |
| else if (prv < seg.second) { | |
| ans += seg.second - prv; | |
| prv = seg.second; | |
| } | |
| } | |
| return ans; | |
| } | |
| }; |