[BOJ 17637 // C++] Count Squares

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17637번 문제인 Count Squares이다.
문제는 아래 링크를 확인하자.

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

17637번: Count Squares

가로간격이 d인 한 쌍의 수직선과 한 쌍의 수평선이 있다면 한 변의 길이가 d인 정사각형을 하나 찾을 수 있다.

 

따라서, 모든 수직선쌍 사이의 거리들을 미리 전부 구해두고, 서로 같은 거리값의 개수를 이용해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int H, V;
int h[1500];
int v[1500];

vector<int> height, width;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> H >> V;
	for (int i = 0; i < H; i++) cin >> h[i];
	for (int i = 0; i < V; i++) cin >> v[i];

	for (int i = 0; i < H; i++) {
		for (int j = i + 1; j < H; j++) {
			height.emplace_back(h[j] - h[i]);
		}
	}
	sort(height.begin(), height.end());
	height.emplace_back(2000000007);
	for (int i = 0; i < V; i++) {
		for (int j = i + 1; j < V; j++) {
			width.emplace_back(v[j] - v[i]);
		}
	}
	sort(width.begin(), width.end());
	width.emplace_back(2000000007);

	ll ans = 0;
	int hh = 0, ww = 0; H = H * (H - 1) / 2, V = V * (V - 1) / 2;
	while (hh < H && ww < V) {
		if (height[hh] < width[ww]) hh++;
		else if (height[hh] > width[ww]) ww++;
		else {
			int cur = height[hh];
			ll cnt1 = 0, cnt2 = 0;
			while (height[hh] == cur) hh++, cnt1++;
			while (width[ww] == cur) ww++, cnt2++;
			ans += cnt1 * cnt2;
		}
	}

	cout << ans;
}