취미로 코딩하기

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

이번에 볼 문제는 백준 14905번 문제인 소수 4개의 합이다.
문제는 아래 링크를 확인하자.

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

모든 소수는 2 이상이므로 주어지는 수가 8보다 작다면 조건을 만족하는 네 수를 찾는 것은 항상 불가능함을 알 수 있다. 아래부터는 주어지는 수가 8 이상이라 가정하자.

prime gap \(g_i\)는 \(i\)번째 소수와 \(i + 1\)번째 소수의 차를 나타내는 수열로, \(i\)번째 소수가 1억 이하일 경우 \(g_i\)의 최댓값은 47326693와 47326913의 차와 같은 220임이 잘 알려져있다. 따라서 1억 이하의 수가 주어질 때 이 수보다 작으면서 가장 큰 소수를 찾는 것은 많아야 220개의 수를 직접 소수판정하는 것으로 해낼 수 있다. 소수판정은 주어진 수의 제곱근 이하의 각 소수들로 나누어보는 것으로 해낼 수 있고 많은 수는 2나 3과 같은 작은 소수로 나누어떨어지므로, 소수들을 미리 에라토스테네스의 체 등으로 전처리해둔다면 이 과정은 충분히 빠르게 진행할 수 있다.

위 지식을 이용하면, 먼저 주어지는 수와 6 이상 차이가 나는 가장 큰 소수를 찾고 주어진 수에서 찾은 수를 뺀 수를 세 소수의 합으로 구성하는 것으로 문제를 해결할 수 있음을 알 수 있다. 한편, 골드바흐의 추측(Goldbach's Conjecture)이 충분히 작은 범위의 양의 정수에 대하여 성립함을 이용하면, 남은 수가 짝수가 되게끔 2 또는 3을 골라 뺀 다음 조건을 만족하는 남은 두 소수를 찾아 남은 문제를 해결할 수 있음을 관찰할 수 있다.

prime gap에 대한 자세한 내용은 링크를 참고하자.

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

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

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

int N;

void solve() {
	if (N < 8) {
		cout << "Impossible.\n";
		return;
	}
	for (int k = N - 6; k > 0; k--) {
		bool chk = 1;
		for (auto &p : P) {
			if (k % p) continue;
			if (k != p) chk = 0;
			break;
		}
		if (chk) {
			cout << k << ' ';
			N -= k;
			break;
		}
	}
	if (N & 1) N -= 3, cout << 3 << ' ';
	else N -= 2, cout << 2 << ' ';
	for (auto &p : P) {
		if (sieve[N - p]) continue;
		cout << p << ' ' << N - p << '\n';
		return;
	}
}

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

	sieveinit();
	while (cin >> N) solve();
}

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

이번에 볼 문제는 백준 11692번 문제인 시그마 함수이다.
문제는 아래 링크를 확인하자.

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

양의 정수 \(n\)이 \(p_1^{k_1} p_2^{k_2}\cdots p_m^{k_m}\)으로 소인수분해될 때, \(n\)의 양의 약수의 합은 \((1+p_1+p_1^2+\cdots +p_1^{k_1}) (1+p_2+p_2^2+\cdots +p_2^{k_2})\cdots (1+p_m+p_m^2+\cdots +p_m^{k_m})\)과 같이 나타낼 수 있음을 기억해내자. (중학교 교육과정)

홀수인 소수 \(p\)에 대하여 \(1+p+p^2+\cdots +p^{k}\)의 값은 \(k\)의 값이 홀수일 때 짝수가 되고 짝수일 때 홀수가 된다. 그리고 \(p=2\)인 경우 \(1+p+p^2+\cdots +p^{k}\)의 값은 항상 홀수가 된다.

따라서 \(n\)의 양의 약수의 합은 \(n\)이 (제곱수) 또는 (제곱수)*2꼴의 수일 때 홀수, 그 외의 경우 짝수가 됨을 알 수 있다.

한편 \(n\) 이하의 제곱수의 개수는 \(O(\sqrt{n})\)개 있으므로, \(10^{12}\) 이하의 각 제곱수와 그 2배 꼴의 수에 대하여 \(n\) 이하인지 하나하나 확인해 문제를 해결할 수 있다.

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

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

ll N;
ll cnt;

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

	cin >> N;
	for (ll i = 1; i < 1000001; i++) {
		if (i * i <= N) cnt++;
		if (i * i * 2 <= N) cnt++;
	}

	cout << N - cnt;
}

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

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

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

각 참가자의 점수를 계산하려면 각 문제의 점수가 어떻게 결정되었는지를 먼저 알아내야 한다. 각 문제의 점수는 각 문제를 해결하지 못한 참가자 수와 같다는 문제 조건을 이용해 먼저 각 문제의 점수를 구하자. 그리고 구한 점수를 이용해 각 참가자의 점수를 구하자. 또한 각 참가자가 해결한 문제 수도 같이 구하자.

이제 각 참가자의 점수와 해결한 문제 수를 정렬 기준으로 세워 정렬하면 \(P\)번째 참가자(필립)의 순위를 구할 수 있다. 이를 구현해 문제를 해결하자.

순위는 0-based가 아닌 1-based값임에 유의하자.

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

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

int N, T, P;
int score[2001];
bool AC[2001][2001];
vector<pair<pair<int, int>, int>> vec;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> T >> P;
	for (int t = 1; t <= T; t++) score[t] = N;
	for (int i = 1; i <= N; i++) {
		for (int t = 1; t <= T; t++) {
			cin >> AC[i][t];
			if (AC[i][t]) score[t]--;
		}
	}

	for (int i = 1; i <= N; i++) {
		int val = 0, cnt = 0;
		for (int t = 1; t <= T; t++) {
			if (AC[i][t]) val += score[t], cnt++;
		}
		vec.emplace_back(make_pair(make_pair(-val, -cnt), i));
	}

	sort(vec.begin(), vec.end());
	for (int i = 0; i < N; i++) {
		if (vec[i].second == P) cout << -vec[i].first.first << ' ' << i + 1;
	}
}

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

이번에 볼 문제는 백준 17254번 문제인 키보드 이벤트이다.
문제는 아래 링크를 확인하자.

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

문제의 내용을 정리하면, 각각의 키보드 이벤트로 출력될 문자들은 (1) 누른 시각이 빠를수록, 누른 시각이 같다면 (2) 키보드 번호가 작을수록 먼저 출력됨을 알 수 있다.

위의 기준으로 전체 키보드 이벤트를 정렬하고, 해당 정렬된 순서대로 각 키보드 이벤트로 출력하게 되는 문자를 구해 문제를 해결하자. 이는 sort, pair등을 이용해 간단하게 구현할 수 있다.

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

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

int N, M;
vector<pair<pair<int, int>, char>> vec;

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

	cin >> N >> M;
	while (M--) {
		int i, j; char c; cin >> i >> j >> c;
		vec.emplace_back(make_pair(make_pair(j, i), c));
	}
	sort(vec.begin(), vec.end());
	for (auto &p:vec) cout << p.second;
}

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

이번에 볼 문제는 백준 1680번 문제인 쓰레기 수거이다.
문제는 아래 링크를 확인하자.

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

가능하다면 지문을 영어 원문으로 읽는 것을 추천한다.

지문에 따르면 쓰레기차의 움직임은 다음을 반복하는 것으로 정리할 수 있다:

1. 더 이상 쓰레기를 실을 지점이 없으면 쓰레기장으로 이동 후 이동을 끝낸다.
2. 다음 쓰레기를 실을 지점으로 이동한다.
3. 현재 쓰레기차에 현 위치의 쓰레기를 실을 수 없다면 쓰레기장으로 돌아갔다 온다.
4. 현 위치의 쓰레기를 싣는다.
5. 현재 쓰레기차의 용량이 가득 찼다면 쓰레기장으로 돌아간다.

어떤 지점의 쓰레기가 \(W\)이고 해당 지점에 처음 도착할 때 쓰레기차에 쓰레기가 있는 경우, 쓰레기차는 (1)먼저 쓰레기를 비우고 돌아온 다음 (2)해당 지점의 쓰레기를 싣고 (3)쓰레기차의 용량이 가득 찼으므로 다시 쓰레기를 비우러 가게 되는 점에 유의해 구현하자.

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

#include <iostream>
using namespace std;

int W, N, cur, ans, x, w;

void solve() {
	cur = ans = 0;
	cin >> W >> N;
	while (N--) {
		cin >> x >> w;
		cur += w;
		if (cur > W) ans += x, cur = w;
		if (cur == W) ans += x, cur = 0;
	}
	if (cur) ans += x;
	cout << ans * 2 << '\n';
}

int T;

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

	cin >> T;
	while (T--) solve();
}

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

이번에 볼 문제는 백준 17423번 문제인 민원이 넘쳐흘러이다.
문제는 아래 링크를 확인하자.

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

각 스피커의 볼륨 \(V\)가 어떤 상수로 정해져있을 때 민원이 들어올지 판단하는 방법이 있을까? 민원이 들어오는 볼륨상태에서 볼륨을 높이면 민원이 들어오고 민원이 들어오지 않는 볼륨에서 볼륨을 낮추면 민원이 들어오지 않는 점을 관찰하면, 위 판단이 가능하면 이 문제를 이진 탐색(또는 parametric search)을 통해 해결할 수 있음을 알 수 있다.

그러면 볼륨이 정해져 있을 때 민원이 들어올지 여부를 어떻게 판단해야 할지 생각해보자. 만약 각 스피커로부터 음악이 들리는 범위가 축과 평행한 사각형 모양이었다면 segment tree와 line sweep 테크닉을 이용해 이를 해결할 수 있을 것이다. 그러나 이 문제에서는 음악이 들리는 범위가 축과 45도를 이루는 사각형 모양을 하고 있다.

그렇다면 좌표평면의 축을 45도 돌려서 생각하면 어떨까? 축을 45도 돌려서 생각하면 스피커로부터 음악이 들리는 범위를 축과 평행한 사각형 모양으로 다룰 수 있게 된다. 또한 단순히 축을 돌리기만 하지 않고 적절한 상수배까지 적용하면 모든 좌표를 정수가 되게끔 할 수 있다. 여기까지 생각해낸다면 남은 문제를 해결하는 방법은 잘 알려져있고, 이를 구현해 문제를 쉽게 해결할 수 있다.

축을 회전해 각 점에 새로운 좌표를 부여할 때, 신경쓰지 않으면 새로운 좌표로 음수가 부여되어 문제가 생길 수 있다는 점에 유의하자.

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

//45도 회전 + sweepline seg + binary search
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int N;
int seg[8388609][2];
int upd(int L, int R, int qL, int qR, int qVal, int sI) {
	if (seg[sI][1]) {
		seg[sI][0] += seg[sI][1] * (R - L + 1);
		if (L < R) seg[sI * 2][1] += seg[sI][1], seg[sI * 2 + 1][1] += seg[sI][1];
		seg[sI][1] = 0;
	}
	if (R < qL || qR < L) return seg[sI][0];
	if (qL <= L && R <= qR) {
		seg[sI][0] += qVal * (R - L + 1);
		if (L < R) seg[sI * 2][1] += qVal, seg[sI * 2 + 1][1] += qVal;
		return seg[sI][0];
	}
	return seg[sI][0] = upd(L, (L + R) / 2, qL, qR, qVal, sI * 2) + upd((L + R) / 2 + 1, R, qL, qR, qVal, sI * 2 + 1);
}

int qry(int L, int R, int qL, int qR, int sI) {
	if (seg[sI][1]) {
		seg[sI][0] += seg[sI][1] * (R - L + 1);
		if (L < R) seg[sI * 2][1] += seg[sI][1], seg[sI * 2 + 1][1] += seg[sI][1];
		seg[sI][1] = 0;
	}
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI][0];
	return qry(L, (L + R) / 2, qL, qR, sI * 2) + qry((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int spow[100000]; int P[100000][2];
vector<pair<pair<int, int>, pair<int, int>>> qvec;

int ansL = 0, ansR = 999999;

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> spow[i];
	for (int i = 0; i < N; i++) cin >> P[i][0] >> P[i][1];

	while (ansL < ansR) {
		memset(seg, 0, sizeof(seg));
		qvec.clear();
		int mid = (ansL + ansR) / 2 + 1;
		for (int i = 0; i < N; i++) {
			int p = spow[i] * mid;
			int &x = P[i][0], &y = P[i][1];
			qvec.emplace_back(make_pair(make_pair(x - y - p, 1), make_pair(x + y - p + 1000000, x + y + p + 999999)));
			qvec.emplace_back(make_pair(make_pair(x - y + p, -1), make_pair(x + y - p + 1000000, x + y + p + 999999)));
		}
		sort(qvec.begin(), qvec.end());

		bool chk = 1;
		for (auto &q:qvec) {
			int L = q.second.first, R = q.second.second;
			if (q.first.second < 0) upd(1, 3000000, L, R, -1, 1);
			else {
				if (qry(1, 3000000, L, R, 1)) {
					chk = 0;
					break;
				}
				upd(1, 3000000, L, R, 1, 1);
			}
		}

		if (chk) ansL = mid;
		else ansR = mid - 1;
	}

	cout << ansL;
}