[BOJ] 백준 22876. 츠바메가에시 (Platinum IV)

UCPC 2021 본선 D번 문제이다.

본선은 정말 괴수들만 진출하는 곳이 맞긴 한가보다.

UCPC 본선 중에서 가장 쉬운 문제들 중 하나라고 한다.

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

22876번: 츠바메가에시

처음에 이 문제에서 tree 배열의 범위를 잘못 생각하여 계속 맞왜틀을 하였다...

---

의식의 흐름 및 해설 / 테스트케이스 첨부

처음에는 단순히 매 순간의 최댓값 3번을 구하면 된다고 생각하여 세그먼트트리를 이용하여 구현하였다.

주의할 점은 좌표의 범위가 0 <= x, y <= 1,000,000 이라는 점.

따라서 나는 아예 각각 +1씩 하여 1<= x, y <= 1,000,001로 접근하였다.

또한, x좌표의 범위는 1<= x <= 1,000,001, y좌표 범위는 1,000,002 <= y <= 2,000,002 로 접근하여 겹치는 부분의 좌표를 0점으로 만드는 update는 아래와 같이 진행했었다.

	for (int i = 0; i <= 1000000; i++) {
		a[i + 1].second = i;
		a[i + 1000002].second = i + 1000002;
	}
	for (int i = 0; i < 3; i++) {
    		// update를 반영하기
		init(1, 1, 2000002);
		ans += tree[1].first;
		int idx = tree[1].second;
		for (int j = 0; j < N; j++) {
			int x = v[j].first.first;
			int y = v[j].first.second;
			int cost = v[j].second;
            		// 이미 1번 벤 좌표들은 이제 점수를 0점으로 만들기
			if (idx <= 1000001 && x == idx) {
				a[x + 1].first -= cost;
				a[y + 1000002].first -= cost;
			}
			else if (idx > 1000001 && y + 1000002 == idx) {
				a[x + 1].first -= cost;
				a[y + 1000002].first -= cost;
			}
		}
	}

그런데 위와 같이 함부로 그리디적으로 진행하면 안된다!

총 3번을 베기 때문에, 현재의 최적해가, 다음의 최적해가 아니기 때문이다. 

이는 현재 구한 해가 다음 구할 해에 영향을 끼치기 때문이다.

 

아래와 같은 반례가 있기 때문이다.

13
1 2 5
2 1 3
2 2 3
2 3 3
2 4 3
3 1 2
3 2 2
3 3 4
3 4 3
4 1 2
4 2 3
4 3 3
4 4 4
ans: 35
wrong: 33

단순 그리디적으로 해결한다면 위와 같이 될 것이다.

 

따라서 모든 경우를 확인해보는 방법으로 진행해야 한다.

 

X축으로 3번 베는 경우,

X축 2번, Y축 1번 베는 경우,

X축 1번, Y축 2번 베는 경우,

Y축으로 3번 베는 경우.

 

코드의 구현량이 늘어날 것 같아, 아예 최댓값과 두번째 최댓값을 리턴하는 세그먼트트리를 만들어서 진행했다.

이 세그먼트트리는 아래 문제에서 만들어볼 수 있다.

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

17408번: 수열과 쿼리 24

Y축으로 1번 베어 제비를 벨 수 있는 모든 경우에 한해 X축 2번을 어떻게 베느냐에 따라 최댓값과 두번째 최댓값을 구하여 가장 최대일 때로 답을 구한다.

 

X축 1번 벨 때 또한 마찬가지이다.

 

이 때, 이미 베어버린 제비 update는 set자료구조를 이용하여 시간복잡도를 줄여서 진행한다.

자세한 내용은 아래 코드를 보자.

 

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
// 좌표의 범위가 0~1,000,000 이므로 1씩 더해 1~1,000,001로 진행.
const int MAX = 1000002;
int N, ans, a[MAX], xList[MAX], yList[MAX], tmpX[MAX], tmpY[MAX];
pi tree[1 << 21];
vector<pii> v;
set<int> S[MAX];
pi merge(pi p1, pi p2) {
	if (p1.first < p2.first)
		swap(p1, p2);
	return { p1.first, max(p1.second, p2.first) };
}
pi query(int node, int s, int e, int left, int right) {
	if (e < left || right < s)
		return { 0, 0 };
	if (left <= s && e <= right)
		return tree[node];
	int mid = (s + e) / 2;
	return merge(query(node * 2, s, mid, left, right)
		,query(node * 2 + 1, mid + 1, e, left, right));
}
void update(int node, int s, int e, int idx, int val) {
	if (e < idx || idx < s)
		return;
	tree[node] = { val, 0 };
	if (s != e) {
		int mid = (s + e) / 2;
		update(node * 2, s, mid, idx, val);
		update(node * 2 + 1, mid + 1, e, idx, val);
		tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y, cost;
		cin >> x >> y >> cost;
		v.push_back({ {x, y}, cost });
		xList[x + 1] += cost;
		yList[y + 1] += cost;
		tmpX[x + 1] = xList[x + 1];
		tmpY[y + 1] = yList[y + 1];
	}
    	// 1. X축, Y축 나란히 3번 베는 경우
	sort(tmpX, tmpX + MAX, greater<int>());
	sort(tmpY, tmpY + MAX, greater<int>());
	ans = max(tmpX[0] + tmpX[1] + tmpX[2],
		tmpY[0] + tmpY[1] + tmpY[2]);
    	// 2. X축방향 1번, Y축 방향 2번
	int res = 0;
	for (int i = 0; i < v.size(); i++) {
		int x = v[i].first.first;
		int y = v[i].first.second;
		int cost = v[i].second;
       		// X축방향으로 벨 때 사라지는 제비를 없애기 위해 set에 저장
		S[y + 1].insert(i);
	}
	for (int i = 1; i <= 1000001; i++) {
		if (!xList[i])
			continue;
		update(1, 1, MAX - 1, i, xList[i]);
	}
	for (int i = 1; i <= 1000001; i++) {
		int tmp = 0;
		if (!S[i].size())
			continue;
        	// x축 방향으로 벨 제비가 있다면 진행
		for (auto it = S[i].begin(); it != S[i].end(); it++) {
            	// x축방향으로 벤 점수 더함
			tmp += v[*it].second;
			xList[v[*it].first.first + 1] -= v[*it].second;
			update(1, 1, MAX - 1, v[*it].first.first + 1, xList[v[*it].first.first + 1]);
		}
        	// y축방향 최댓값 두개 더함
		pi ret = query(1, 1, MAX - 1, 1, MAX - 1);
		tmp += ret.first + ret.second;
		for (auto it = S[i].begin(); it != S[i].end(); it++) {
			xList[v[*it].first.first + 1] += v[*it].second;
			update(1, 1, MAX - 1, v[*it].first.first + 1, xList[v[*it].first.first + 1]);
		}
		res = max(res, tmp);
	}
	ans = max(res, ans);
    	// 3. Y축방향 1번, X축 방향 2번
	res = 0;
    	// 초기화
    memset(tree, 0, sizeof(tree));
	for (int i = 1; i <= 1000001; i++) {
		S[i].clear();
	}
	for (int i = 0; i < v.size(); i++) {
		int x = v[i].first.first;
		int y = v[i].first.second;
		int cost = v[i].second;
        	// y축방향으로 벨 때 사라지는 제비를 없애기 위해 set에 저장
		S[x + 1].insert(i);
	}
	for (int i = 1; i <= 1000001; i++) {
		if (!yList[i])
			continue;
		update(1, 1, MAX - 1, i, yList[i]);
	}
	for (int i = 1; i <= 1000001; i++) {
		int tmp = 0;
		if (!S[i].size())
			continue;
        	// y축 방향으로 벨 제비가 있다면 진행
		for (auto it = S[i].begin(); it != S[i].end(); it++) {
			tmp += v[*it].second;
			yList[v[*it].first.second + 1] -= v[*it].second;
            	// y축방향으로 벤 점수 더함
			update(1, 1, MAX - 1, v[*it].first.second + 1, yList[v[*it].first.second + 1]);
		}
         	// x축방향 최댓값 두개 더함
		pi ret = query(1, 1, MAX - 1, 1, MAX - 1);
		tmp += ret.first + ret.second;
		for (auto it = S[i].begin(); it != S[i].end(); it++) {
			yList[v[*it].first.second + 1] += v[*it].second;
			update(1, 1, MAX - 1, v[*it].first.second + 1, yList[v[*it].first.second + 1]);
		}
		res = max(res, tmp);
	}
	ans = max(res, ans);
	cout << ans << "\n";
}

---

문제 자체가 재밌어서 되게 흥미롭게 푼 문제이다.

믿고 푸는 UCPC 문제셋!