취미로 코딩하기

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

이번에 볼 문제는 백준 24731번 문제인 XOR-ABC이다.
문제는 아래 링크를 확인하자.

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

1 이상 \(2^K-1\) 이하의 서로 다른 두 정수 \(A\)와 \(B\)를 골랐을 때, \(A\)와 \(B\)를 xor연산해 얻을 수 있는 정수 \(C\)는 \(A\)와 \(B\)와는 항상 다른 값인 1 이상 \(2^K-1\) 이하의 정수가 된다는 점을 관찰하자. 그리고 이 세 수를 크기순으로 정렬해 나타내면 이는 문제에서 찾는 하나의 쌍이 됨을 확인하자.

이와 같은 구성의 세 수를 얻는 방법은 두 정수를 \(A\)와 \(B\), \(B\)와 \(A\), \(A\)와 \(C\), \(C\)와 \(A\), \(B\)와 \(C\), \(C\)와 \(B\)와 같이 고르는 6가지가 존재한다. 이를 이용해 정수를 고르는 경우의 수를 얻을 수 있는 식을 세워 문제를 해결하자.

답을 주어진 소수로 나눈 나머지를 구하면 되므로 필요하면 모듈로 곱셈 역원을 이용해 나눗셈 연산을 진행하자.

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

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

ll K;
ll x = 1, b = 2;
ll A, B;

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

	cin >> K;
	while (K) {
		if (K & 1) {
			x = x * b % 1000003;
		}
		b = b * b % 1000003;
		K >>= 1;
	}
	A = x - 1, B = x - 2;
	if (A < 0) A += 1000003;
	if (B < 0) B += 1000003;
	cout << A * B * 833336 % 1000003;
}

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

이번에 볼 문제는 백준 30679번 문제인 별 가두기이다.
문제는 아래 링크를 확인하자.

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

1열에 있는 각 칸에 별을 둘 때 격자 밖으로 빠져나가지 않는 칸의 수를 세는 문제이다.

각 칸으로부터 40001회 이동한 뒤에서 격자 안에 있다면 별은 격자를 빠져나가지 않을 것임을 관찰하자. 비둘기집의 원리에 의해 위 이동과정에는 같은 칸에서 같은 방향을 바라보고 있는 상황이 반드시 존재하므로 움직임이 반복됨을 알 수 있기 때문이다.

따라서 1열의 각 칸에 별을 올려두고 40001회씩 이동을 시도하는 시뮬레이션을 통해 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int R, C;
int A[100][100];
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};
int ans;
int acnt[100];

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> A[r][c];
		}
	}

	for (int r = 0; r < R; r++) {
		int rr = r, cc = 0; bool chk = 1;
		for (int k = 0; k < 40001; k++) {
			int rval = dr[k % 4] * A[rr][cc];
			int cval = dc[k % 4] * A[rr][cc];
			rr += rval, cc += cval;
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) {
				chk = 0;
				break;
			}
		}
		if (chk) ans++, acnt[r] = 1;
	}

	cout << ans << '\n';
	for (int r = 0; r < R; r++) {
		if (acnt[r]) cout << r + 1 << ' ';
	}
}

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

이번에 볼 문제는 백준 16508번 문제인 전공책이다.
문제는 아래 링크를 확인하자.

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

전공책의 개수 \(N\)이 16 이하임을 확인하자. 즉 전공책을 고르는 경우의 수는 \(2^N\), 즉 65536가지로 충분히 적음을 알 수 있다.

따라서 각각의 모든 전공책을 고르는 경우의 수를 방문해 (1) 원하는 문자열을 만들 수 있는지 확인하고 (2) 만들 수 있는 경우들의 전공책 가격의 합의 최솟값을 구해 문제를 해결할 수 있다.

글쓴이는 고른 책들의 이름에 포함된 각 문자들의 수를 관리해 원하는 문자열의 각 문자의 수와 비교하는 방식으로 (1) 과정을 구현하였다.

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

#include <iostream>
using namespace std;

string s;
int N;
int C[16]; string ss[16];
int X[128];
int cnt[128], total;
int ans = 1000000007;
void func(int idx) {
	if (idx == N) {
		bool chk = 1;
		for (char c = 'A'; c <= 'Z'; c++) {
			if (cnt[c] < X[c]) {
				chk = 0;
				break;
			}
		}
		if (chk) ans = min(ans, total);
		return;
	}
	func(idx + 1);
	for (auto &l:ss[idx]) cnt[l]++;
	total += C[idx];
	func(idx + 1);
	total -= C[idx];
	for (auto &l:ss[idx]) cnt[l]--;
}

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

	cin >> s;
	for (auto &l:s) X[l]++;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> C[i] >> ss[i];
	}

	func(0);
	if (ans < 1000000007) cout << ans;
	else cout << -1;
}

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

이번에 볼 문제는 백준 22662번 문제인 Pi is Three이다.
문제는 아래 링크를 확인하자.

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

글쓴이는 Stern-Brocot tree(Farey sequence)를 이용하여 문제를 해결하였다. 해당 개념을 알고 있다고 가정하고 풀이를 서술한다.

Farey sequence에서 인접한 두 항 \(L=\frac{A_1}{A_2}\)과 \(R=\frac{B_1}{B_2}\)이 사이에 원주율에서 3을 뺀 값 \(P\)을 포함하고 있다고 해보자. 이때, \(P-L\)과 \(R-P\) 중 작은 값보다 더 \(P\)에 가까운 분수의 분모는 Farey Sequence의 성질에 의해 \(A_2\) 및 \(B_2\)보다 큼을 관찰하자.

위 성질을 이용하면 Stern-Brocot tree를 따라 \(P\)에 가까운 분수를 찾아나가는 것으로 문제에서 요구하는 분수를 찾을 수 있게 된다. 이를 이용해 문제를 해결하자.

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

//stern-brocot tree
#include <iostream>
#include <cmath>
using namespace std;
typedef long double ld;
typedef long long ll;

const ld PI3 = acosl(-1) - 3;

ll A1 = 0, A2 = 1, B1 = 1, B2 = 1, C1, C2;
ld x;

void solve() {
	A1 = 0, A2 = 1, B1 = 1, B2 = 1;
	while (PI3 * A2 - A1 > x * A2 && B1 - PI3 * B2 > x * B2) {
		C1 = A1 + B1, C2 = A2 + B2;
		if (PI3 * C2 < C1) B1 = C1, B2 = C2;
		else A1 = C1, A2 = C2;
	}
	if (PI3 * A2 - A1 < x * A2) cout << A2 * 3 + A1 << '/' << A2 << '\n';
	else cout << B2 * 3 + B1 << '/' << B2 << '\n';
}

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

	cin >> x;
	while (x) {
		solve();
		cin >> x;
	}
}

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

이번에 볼 문제는 백준 11690번 문제인 LCM(1, 2, ..., n)이다.
문제는 아래 링크를 확인하자.

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

1 이상 \(n\) 이하의 정수들의 최소공배수를 구하는 문제이다.

각 소수 \(p\)는 이 최소공배수에 몇 번 곱해져있을까? 이 값을 \(k\)라 할 때, \(k\)는 \(p^k\le n\)를 만족시키는 가장 큰 정수가 될 것이다. 이와 같은 \(p^k\)는 1 이상 \(n\) 이하의 정수이며 따라서 구하는 최소공배수는 이 수의 배수여야하기 때문이다.

\(n\) 이하의 모든 소수에 대하여 해당 소수가 최소공배수에 최대 몇 개가 포함되는지를 각각 구해 이를 곱하는 것으로 문제의 답을 구하자. \(n\) 이하의 모든 소수를 구하는 것은 에라토스테네스의 체를 이용하면 빠르게 해낼 수 있다. 이 과정에서 메모리초과가 나지 않게끔 유지하자. 각 수가 소수인지 여부만을 저장하는 것은 각수마다 1비트만 이용해도 충분함을 이용하면 이를 어렵지 않게 해낼 수 있을 것이다.

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

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

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

int N;
unsigned int ans = 1;

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

	sieveinit();
	
	cin >> N;
	for (int i = 2; i < 99999999; i++) {
		if (sieve[i]) continue;
		int NN = N;
		while (NN >= i) {
			NN /= i;
			ans *= i;
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 19592번 문제인 장난감 경주이다.
문제는 아래 링크를 확인하자.

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

단독 우승만을 목표로 하는데 다른 참가자의 자동차들은 일정한 속력으로 이동하므로, 다른 참가자의 자동차는 가장 빠른 속력을 가진 것만을 신경써도 충분하다. 해당 차와의 비교만을 생각하자.

먼저, 부스터를 사용하지 않은 상태로도 상대 차를 앞설 수 있는 경우 답은 0이 된다.

그렇지 않을 경우 문제의 답은 \(Y\) 이하의 각 부스터속도에 대하여 상대 차를 앞설 수 있는 \(Y\)가 있을 경우 그 최솟값, 그렇지 않을 경우 -1이 된다.

가능한 \(Y\)의 후보는 많아야 100만개이고, 테스트케이스도 많아야 10개이므로 가능한 모든 \(Y\)값을 확인해 문제를 해결하자.

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

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

ll N, X, Y;
ll V, VV;

void solve() {
	V = 0;
	cin >> N >> X >> Y;
	for (int i = 1; i < N; i++) {
		ll v; cin >> v;
		V = max(V, v);
	}

	cin >> VV;
	if (V < VV) cout << 0 << '\n';
	else {
		for (ll v = VV + 1; v <= Y; v++) {
			ll d = X - V, dd = X - v;
			if (d * VV > dd * V) {
				cout << v << '\n';
				return;
			}
		}

		cout << -1 << '\n';
	}
}

int T;

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

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