[C++] 백준(BOJ) - 5419 : 북서풍

15 May 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 5419 : 북서풍(링크)

강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다.

작은 섬이 여러 개 있는 바다가 있다. 섬은 좌표 평면의 한 점으로 나타낼 수 있다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫째 줄에는 섬의 수 n (1 ≤ n ≤ 75000)이 주어진다. 다음 n개 줄에는 각 섬의 좌표 $x_i, y_i$가 주어진다. 두 섬의 좌표가 같은 경우는 없다. ($-10^9 ≤ x_i, y_i ≤ 10^9$)

출력

각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다.

알고리즘

1. 펜윅트리

풀이

• 브루트포스 풀이
  • $O(N^2)$, n <= 75000 50억 이상

• 문제 단순화 => 정렬을 진행해보기

• 핵심 아이디어
  • 탐색을 한번에 진행하기, x축 한정으로 누적합을 구하는 방식
  • y축 뒤집기
  • 동적 배열
    • counting을 하며 배열 값이 변경 됨. 펜윅 트리
  • 좌표 범위 (-10^9 < x, y < 10^9)
    • x축은 이미 정렬 됨
    • y축만 신경쓰기
      • 좌표 압축을 통해 인덱스로만 탐색
      • 이분탐색을 사용해서 인덱스 찾기

코드

// BOJ - 5419 : 북서풍
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n, x, y;
vector<int> tree, _y;
vector<pair<int, int>> a;

int sum(int idx)
{
	int res = 0;
	while (idx > 0)
	{
		res += tree[idx];
		idx -= (idx & -idx);
	}
	return res;
}

void update(int pos, int value)
{
	int idx = pos;
	while (idx <= n)
	{
		tree[idx] += value;
		idx += (idx & -idx);
	}
	return;
}

int find_idx(vector<int>& _y, int value)
{
	int lo = 0, hi = _y.size() - 1;
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (_y[mid] == value) return mid;
		if (_y[mid] < value) lo = mid + 1;
		else hi = mid - 1;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> t;
	while (t--)
	{
		cin >> n;
		a.clear(); _y.clear(); tree.clear();
		tree.resize(n + 1);

		for (int i = 0; i < n; i++)
		{
			cin >> x >> y;
			a.push_back({ x, y * -1 });
			_y.push_back(y * -1); // y값을 이분탐색을 위해 따로 배열에 저장 (-10^9 ~ 10^9 배열은 너무 크다)
		}

		sort(a.begin(), a.end());
		sort(_y.begin(), _y.end());
		ll res = 0;
		update(find_idx(_y, a[0].second) + 1, 1);
		for (int i = 1; i < n; i++)
		{
			int idx = find_idx(_y, a[i].second) + 1;
			res += 1LL * sum(idx);
			update(idx, 1);
		}
		cout << res << '\n';
	}
	return 0;
}

평가

• 어렵다,,,
• 펜윅트리에 대한 복습은 추후 다시 진행 하고 업데이트한다