취미로 코딩하기

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

이번에 볼 문제는 백준 9464번 문제인 직사각형 집합이다.
문제는 아래 링크를 확인하자.

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

Pythagorean Triple (a,b,c) (a<b<c를 만족) 중 a와 b가 서로 소인 쌍을 Primitive Pythagorean Triple이라 한다.

주어진 철사를 이용해 가장 많은 직사각형을 만드는 방법은 Primitive Pythagorean Triple의 2a+2b 값을 작은 순으로 골라 두 인접한 변의 길이가 a와 b인 직사각형을 만들어나가는 것이 임을 관찰하자. (주어진 철사를 전부 소비할 필요는 없음에 유의하자.)

글쓴이는 a+b의 값이 5000 이하인 Primitive Pythagorean Triple들을 미리 전처리로 구해 i개의 직사각형을 만들기 위해 필요한 최소 철사길이를 나타내는 배열을 작성해두고 문제에서 주어지는 쿼리마다 이진탐색을 통해 문제의 답을 구해주었다.

아래는 제출한 소스코드에 사용된 배열을 구하기 위해 작성한 코드이다.

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

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

ll sq_rt[100000001];

int vecsize;
vector<ll> vec;

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

	for (ll i = 1; i < 10000; i++) {
		sq_rt[i * i] = i;
		for (ll j = 1; j < i; j++) {
			ll& k = sq_rt[i * i - j * j];
			if (k && j < k && gcd(i,gcd(j,k)) == 1 && j + k < 5000) vec.emplace_back(j + k);
		}
	}

	sort(vec.begin(), vec.end());
	vecsize = vec.size();
	for (int i = 1; i < vecsize; i++) vec[i] += vec[i - 1];

	cout << vecsize << '\n';
	for (int i = 0; i < vecsize; i++) cout << vec[i] << ',';
}