[BOJ] 백준 17131. 여우가 정보섬에 올라온 이유 (Platinum IV)

스코페를 치른 이후 LCA와 segtree를 연습하고 싶은 마음에 푼 문제이다.

문제는 다음과 같다.

www.acmicpc.net/problem/17131

17131번: 여우가 정보섬에 올라온 이유

저번에 북서풍 문제, 화성지도 문제를 풀어서 세그먼트트리 with 스위핑 문제를 경험해서 그런지 이 문제 또한 아이디어 자체는 세그먼트트리가 잘 떠올랐다.

북서풍 문제랑 상당히 유사한 아이디어로 풀면 되지 않을까.

심지어 좌표압축을 할 필요조차 없다.

 

그런데... 난 이문제에서 엄청나게 많은 맞왜틀을 겪었다. (아직도 그 이유는 찾지 못했다. slack, 질문게시판에 물어봤음에도 불구하고 말이다.)

 

참고로 다른 블로그들은 비재귀 세그먼트트리 (인덱스 트리)로 푼 글이 대부분이길래, 난 재귀로 푼 코드를 포스팅에 올려본다. (애초에 내가 재귀로만 푸는 타입이어서 그렇게 푼거긴 하다ㅋㅋ)

---

의식의 흐름 및 해설

1. 먼저, N의 범위가 20만이므로, O(N^2) 이상의 알고리즘은 불가능하다. O(N) 또는 O(NlgN) 등의 알고리즘을 떠올려야 한다. 다행히 이 문제같은 경우 세그먼트트리를 이용해야 함이 잘 보인다. (아직 잘 보이지 않는다면 아래에 보이는 북서풍 문제를 미리 풀고오자. 이 문제와 비슷한 문제이다.)
2. 점들을 입력받고 y좌표를 오름차순으로, y좌표가 같다면 x좌표를 오름차순으로 정렬해준다. O(NlgN)
3. 세그먼트트리에는 x좌표에 따른 별의 개수를 담아준다. 미리 담아주는 이유는, 나중에 쿼리마다 저장하게 되면 x좌표가 자신보다 작은 점들의 개수, 자신보다 큰 점들의 개수를 구하기 위해 더 많은 구현을 해야 하기 때문이다. 미리 담아둘 경우, 세그먼트트리를 이용해 바로 자신보다 x좌표가 작은 점들의 개수, 큰 점들의 개수를 구할 수 있다.
4. 같은 y좌표끼리는 V자형 별자리를 만들 수 없으므로 update로 제거해준다. (update로 제거해주지 않고 map 자료구조를 이용한 코드는 이유는 아직 모르겠지만 WA를 받았다.) for문으로 제거해주면 되는데, for문 안에 for문이 있다고 시간복잡도가 늘어나진 않는다. 어차피 y좌표가 달라질 때에만 한번에 이 작업을 실시해주기 때문이다.
5. 세그먼트트리에는 x좌표에 있는 별의 개수를 담는다. 왼쪽 쿼리로 0 ~ (현재 x좌표 -1)만큼, 오른쪽 쿼리로 (현재 x좌표 +1) ~ MAX (-200000을 0으로 기준잡는다면 400001이 MAX가 되겠다.)를 구해준 후 둘이 곱한 값을 더해준다.

www.acmicpc.net/problem/5419

5419번: 북서풍

 

테스트케이스 첨부

www.acmicpc.net/board/view/66408

글 읽기 - 반례가 무엇일까요? 12%에서 틀립니다

위 질문글 한번씩 봐주시면 감사하겠습니다. 아직도 저 코드가 왜 틀렸는지 모르겠습니다.

y좌표가 같고 x좌표가 다른 점들의 개수를 빼주는 로직만 좀 다르게 한 코드입니다.

같은 좌표가 입력으로 주어지지 않는 한, 틀린 반례를 찾지 못하겠습니다.

 

틀린 코드 (맞왜틀 코드)

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int MAX = 200001;
const ll MOD = 1e9 + 7;
struct Point {
	int x, y;
};
Point p[MAX];
vector<int> v;
map<int, int> m;
ll N, ans, tree[1 << 20];
bool cmp(const Point& p1, const Point& p2) {
	if (p1.y == p2.y)
		return p1.x < p2.x;
	return p1.y < p2.y;
}
ll query(int node, int s, int e, int left, int right) {
	if (e < left || right < s)
		return 0;
	if (left <= s && e <= right)
		return tree[node];
	int mid = (s + e) / 2;
	return 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 (idx < s || e < idx)
		return;
	tree[node] += val;
	if (s != e) {
		int mid = (s + e) / 2;
		update(node * 2, s, mid, idx, val);
		update(node * 2 + 1, mid + 1, e, idx, val);
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> p[i].x >> p[i].y;
		update(1, 0, MAX * 2 - 1, p[i].x + 200000, 1);
		v.push_back(p[i].x);
		// 같은 y좌표 개수를 구하기 위함
		m[p[i].y + 200000]++;
	}
	sort(p, p + N, cmp);
	sort(all(v));
	ll cnt2 = (ll)m[p[0].y + 200000] - 1;
	for (int i = 0; i < N; i++) {
		if (i && p[i].y != p[i - 1].y) {
			cnt2 = (ll)m[p[i].y + 200000] - 1;
		}
		ll left = query(1, 0, MAX * 2 - 1, 0, p[i].x + 200000 - 1) % MOD;
		ll right = query(1, 0, MAX * 2 - 1, p[i].x + 200000 + 1, MAX * 2 - 1) % MOD;
		// 같은 y좌표 개수 빼줌
		ans += left * (right - cnt2);
		ans %= MOD;
		update(1, 0, MAX * 2 - 1, p[i].x + 200000, -1);
		// 오른쪽에 있는 같은 y좌표는 빠짐
		cnt2--;
	}
	cout << ans << "\n";
}

맞은 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int MAX = 400001;
const ll MOD = 1e9 + 7;
struct Point {
	ll x, y;
};
Point p[MAX];
vector<ll> v;
ll N, ans, tree[1 << 21];
bool cmp(const Point& p1, const Point& p2) {
	if (p1.y == p2.y)
		return p1.x < p2.x;
	return p1.y < p2.y;
}
ll query(int node, int s, int e, int left, int right) {
	if (e < left || right < s)
		return 0;
	if (left <= s && e <= right)
		return tree[node];
	int mid = (s + e) / 2;
	return (query(node * 2, s, mid, left, right)
		+ query(node * 2 + 1, mid + 1, e, left, right)) % MOD;
}
void update(int node, int s, int e, int idx, ll val) {
	if (idx < s || e < idx)
		return;
	tree[node] += val;
	if (s != e) {
		int mid = (s + e) / 2;
		update(node * 2, s, mid, idx, val);
		update(node * 2 + 1, mid + 1, e, idx, val);
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> p[i].x >> p[i].y;
		update(1, 0, MAX, p[i].x + 200000, 1);
		v.push_back(p[i].x);
	}
	sort(p, p + N, cmp);
	sort(all(v));
	ll num = MOD;
	for (int i = 0; i < N; i++) {
		if (num != p[i].y) {
			num = p[i].y;
			for (int j = i; j < N; j++) {
				if (p[j].y != num)
					break;
				update(1, 0, MAX, p[j].x + 200000, -1);
			}
		}
		ll left = query(1, 0, MAX, 0, p[i].x + 200000 - 1) % MOD;
		ll right = query(1, 0, MAX, p[i].x + 200000 + 1, MAX * 2 - 1) % MOD;
		ans += left * right;
		ans %= MOD;
	}
	cout << ans << "\n";
}

---

WA를 너무 많이 받아 재밌는 문제이지만, 개인적으로 굉장히 스트레스를 많이 받은 문제이다.

틀린 이유를 알 수 없는 점이 나를 굉장히 미치게 하는 것 같다.

 

그럼에도 이 문제가 나에게 좋았던 이유는 세그먼트트리를 이용한 스위핑 문제에서 적절한 아이디어로 접근방법이 맞았기 때문에 희열을 느꼈기 때문이다.

 

세그먼트트리를 자유자재로 다룰 수 있는 그날이 언젠간 올까?