취미로 코딩하기

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

이번에 볼 문제는 백준 15330번 문제인 Parallel Lines이다.
문제는 아래 링크를 확인하자.

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

\(2N\)개의 점을 짝지어 \(N\)개의 선분을 구성하는 방법의 수는 \((2N-1)\cdot (2N-3)\cdots 5 \cdot 3 \cdot 1\)과 같다. \(N=8\)일 경우 이 값은 2027025로 충분히 작아 완전탐색이 가능함을 알 수 있다.

위 내용을 관찰하는 것은 어렵지 않다. 각 점에 번호를 1부터 \(2N\)까지 부여하자. 결국 모든 점은 선분 구성에 사용되어야하므로, 현재 쌍이 정해지지 않은 가장 작은 번호의 점의 짝을 다른 점을 골라 주는 것을 반복하는 과정을 잘 생각해보면 위의 식을 쉽게 유도할 수 있을 것이다.

이제 가능한 모든 선분 구성에 대하여 평행한 선분의 쌍의 개수를 직접 세고, 그중 최댓값을 구해 문제를 해결하자. 문제 조건에 따라 어떤 세 점도 한 직선 위에 있지 않으므로 이 부분 또한 큰 예외처리 없이 구현할 수 있다. 구현에 따라 축과 평행한 선분이 있을 경우의 판정에 유의해 구현하자.

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

#include <iostream>
#include <vector>
using namespace std;

int N, NN;
int P[16][2];
int ans;
vector<pair<int, int>> vec;
bool visited[16];

void func(int n) {
	if (n == NN) {
		int cnt = 0;
		for (int i = 0; i < NN; i++) {
			for (int j = i + 1; j < NN; j++) {
				if (!vec[i].second && !vec[j].second) cnt++;
				else if (!vec[i].second || !vec[j].second) continue;
				else if (vec[i].first * vec[j].second == vec[i].second * vec[j].first) cnt++;
			}
		}
		ans = max(ans, cnt);
		return;
	}

	int i = 0;
	while (visited[i]) i++;
	visited[i] = 1;
	for (int j = i + 1; j < N; j++) {
		if (visited[j]) continue;
		vec.emplace_back(make_pair(P[j][1] - P[i][1], P[j][0] - P[i][0]));
		visited[j] = 1;
		func(n + 1);
		visited[j] = 0;
		vec.pop_back();
	}
	visited[i] = 0;
}

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

	cin >> N; NN = N / 2;
	for (int i = 0; i < N; i++) cin >> P[i][0] >> P[i][1];
	func(0);

	cout << ans;
}

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

이번에 볼 문제는 백준 11525번 문제인 Farey Sequence Length이다.
문제는 아래 링크를 확인하자.

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

주어진 수열에서 (\(\frac{0}{1}\)을 제외하면) 분모가 \(n\)인 분수는 분자로 \(n\) 이하임과 동시에 \(n\)과 서로소인 양의 정수만을 가짐을 관찰하자. 따라서 \(n<N\)인 수열에서 분모가 \(n\)인 분수의 개수는 \(\phi(n)\)과 같음을 알 수 있다. (단, \(n=1\)의 경우는 2이다.)

10000 이하의 양의 정수들에 대하여 euler phi함수의 값을 미리 계산한 다음 prefix sum을 구해 문제를 해결하자.

여담으로, \(n\)차 페리 수열(Farey Sequence of order \(n\))은 0 이상 1 이하의 유리수 중 분모가 \(n\) 이하인 기약분수로 나타낼 수 있는 수를 오름차순으로 나열한 수열이다. 이 수열은 독특한 성질이 많아 유리수 관련 문제를 풀 때 종종 사용하기 좋으므로 스턴-브로콧 트리(Stern-Brocot Tree)와 함께 잘 알아두면 좋은 개념이다.

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

// Euler-phi
#include <iostream>
using namespace std;

int A[10001];

void init() {
	A[0] = 1;
	for (int i = 1; i < 10001; i++) {
		int ii = i, val = i;
		for (int k = 2; k * k <= ii; k++) {
			if (ii % k) continue;
			val = val / k * (k - 1);
			while (!(ii % k)) ii /= k;
		}
		if (ii > 1) val = val / ii * (ii - 1);
		A[i] = A[i - 1] + val;
	}
}

int T, idT, x;

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

	init();
	cin >> T;
	while (T--) {
		cin >> idT >> x;
		cout << idT << ' ' << A[x] << '\n';
	}
}

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

이번에 볼 문제는 백준 25823번 문제인 조합의 합의 합이다.
문제는 아래 링크를 확인하자.

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

\(n\)의 값이 고정되어 있을 때, 다음 식이 성립한다:
\(\sum_{n}^{k=0}\binom{n}{k}^2=\binom{2n}{n}\)

\(n\)행 \(n\)열의 칸을 가진 격자의 좌하단 칸에서 우상단 칸까지 가는 최단경로의 경우의 수(우변)은 좌상단 칸과 우하단 칸을 잇는 대각선 위의 각 칸을 지나는 경우의 수의 합(좌변)과 같다는 점을 관찰하면 위 식이 자명함을 알 수 있을 것이다.

따라서 3 이상 \(M\) 이하의 각 정수 \(m\)에 대하여 \(\binom{2m}{m}\)의 값을 빠르게 구해 문제를 해결하자. 이를 구하는 방법은 다양하므로, 자신이 익숙한 방법을 사용하자.

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

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

int fact[400001];
int invfact[400001];

void finit() {
	fact[0] = 1;
	for (int i = 1; i < 400001; i++) {
		fact[i] = (ll)fact[i - 1] * i % 1000000007;
	}
	invfact[0] = invfact[1] = 1;
	for (int i = 2; i < 400001; i++) {
		invfact[i] = 1000000007 - (ll)(1000000007 / i) * invfact[1000000007 % i] % 1000000007;
	}
	for (int i = 1; i < 400001; i++) invfact[i] = (ll)invfact[i - 1] * invfact[i] % 1000000007;
}

int comb(int N, int R) {
	return (ll)fact[N] * (((ll)invfact[R] * invfact[N - R]) % 1000000007) % 1000000007;
}

int M;
int ans;

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

	finit();

	cin >> M;
	for (int m = 3; m <= M; m++) {
		ans += comb((m) * 2, m);
		if (ans > 1000000006) ans -= 1000000007;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 26090번 문제인 완전한 수열이다.
문제는 아래 링크를 확인하자.

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

길이 \(N\)의 수열에는 \(N(N-1)/2\)가지 연속 부분 수열이 존재한다. 또한 각 연속 부분 수열에 포함되는 수의 합은 prefix sum을 전처리해두는 것으로 매번 \(O(1)\)에 계산할 수 있다.

따라서 이 문제는 주어진 수열의 모든 연속 부분 수열을 살펴보며 해당 부분 수열의 길이가 소수인지, 그리고 그 합이 소수인지를 판정해 조건을 만족하는 수열의 수를 세는 것으로 해결할 수 있다. 이 때, 나올 수 있는 합의 최댓값인 100만 이하의 모든 수를 에라토스테네스의 체 등으로 먼저 전처리해두면 위 과정을 빠르게 진행할 수 있다.

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

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<int> P;
bool sieve[1000001];
void sieveinit() {
	sieve[0] = sieve[1] = 1;
	for (int i = 2; i * i < 1000001; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 1000001; j += i) sieve[j] = 1;
	}
	for (int i = 2; i <= N; i++) {
		if (sieve[i]) continue;
		P.emplace_back(i);
	}
}

int A[501];
int ans;

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


	cin >> N;
	sieveinit();
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		A[i] += A[i - 1];
	}

	for (auto &p : P) {
		for (int i = p; i <= N; i++) {
			if (!sieve[A[i] - A[i - p]]) ans++;
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 10407번 문제인 2 타워이다.
문제는 아래 링크를 확인하자.

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

2의 짝수 거듭제곱은 4의 거듭제곱의 형태로 항상 바꿔쓸 수 있다. 4는 3+1과 같으므로 4의 거듭제곱, 쯕 2의 짝수 거듭제곱은 3으로 나눈 나머지가 항상 1이 됨을 관찰하자.

높이가 2 이상인 2 타워는 항상 2의 짝수 거듭제곱의 형태로 정리할 수 있으므로 문제의 답은 \(H\)가 1인 경우 2, 그 외의 경우 1임을 알 수 있다.

위의 내용을 구현해 문제를 해결하자.

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

#include <iostream>
#include <string>
using namespace std;

string s;

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

	cin >> s;
	if (s == "1") cout << 2;
	else cout << 1;
}

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

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

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

페르마의 마지막 정리(Fermat's Last Theorem)을 이용하는 문제이다. 이 정리는 3 이상의 정수 \(n\)에 대하여 \(a^n+b^n=c^n\)을 만족하는 세 양의 정수 \(a\), \(b\), \(c\)가 존재하지 않는다는 내용을 담고 있다. 이 정리의 증명은 매우 어렵지만 그 내용은 널리 알려져있으므로 결과를 잘 알아두자.

위 정리에 따라 \(x\), \(y\), \(z\) 중 적어도 하나가 0이 아니라면 \(j>2\)인 경우 조건을 만족하는 쌍이 하나도 없음을 알 수 있다. 따라서 다음과 같은 모든 경우를 생각하는 것으로 문제를 해결할 수 있다:

(1) \(j=2\)인 경우

(2) \(j>2\)이고 \(x=0\)인 경우

각 경우의 tuple의 개수를 각각 구해 합쳐 문제의 답을 구하자.

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

#include <iostream>
using namespace std;

int N, M;
int ans;

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

	cin >> N >> M;
	for (int i = 0; i <= N; i++) {
		for (int j = i; j <= N; j++) {
			for (int k = j; k <= N; k++) {
				if (i * i + j * j == k * k) ans++;
			}
		}
	}

	cout << ans + (M - 2) * (N + 1);
}