취미로 코딩하기

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

이번에 볼 문제는 백준 24292번 문제인 РАЗДЕЛЯЙ и ВЛАДЕЙ이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/probelm/24292 

주어진 연산으로 \(a\)와 \(b\)는 곱이 \(ab\)와 같은 두 양의 정수로 바꿀 수 있다. 이 때 어떤 수 \(g\)가 \(a\)의 약수이면서 동시에 \(b\)의 약수가 되려면 \(g^2\)는\(ab\)의 약수여야 함을 관찰하자.

따라서 이 문제는 \(ab\)의 가장 큰 제곱수 인수를 구하는 문제가 된다. \(a\)와 \(b\)는 각각 2000000 이하이므로 두 수를 각각 소인수분해하여 \(ab\)의 가장 큰 제곱수 인수를 구하자.

각 수의 약수인 소수를 저장해놓은 배열은 에라토스테네스의 체를 만드는 것과 같은 방식으로 얻을 수 있으며, 이 배열을 미리 전처리해둘 경우 각 정수 \(n\)의 소인수분해를 \(O(\lg n)\)에 해낼 수 있다. 이를 이용해 소인수분해를 빠르게 해내자.

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

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

int sieve[2000001];
void sieveinit() {
	sieve[1] = 1;
	for (int i = 2; i < 2000001; i++) {
		if (sieve[i]) continue;
		for (int j = i; j < 2000001; j += i) sieve[j] = i;
	}
}
int N, Q;

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

	sieveinit();
	cin >> N >> Q;
	while (Q--) {
		vector<int> vec;
		int A, B; cin >> A >> B;
		while (A > 1) {
			vec.emplace_back(sieve[A]);
			A /= sieve[A];
		}
		while (B > 1) {
			vec.emplace_back(sieve[B]);
			B /= sieve[B];
		}
		sort(vec.begin(), vec.end());
		int old = 1, ans = 1;
		for (auto &x:vec) {
			if (old == x) {
				ans *= x;
				old = 1;
			}
			else old = x;
		}
		cout << ans << ' ';
	}
}

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

이번에 볼 문제는 백준 19583번 문제인 싸이버개강총회이다.
문제는 아래 링크를 확인하자.

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

"개강총회 시작시각 이하의 시각에 채팅을 친 사람의 집합"과 "개강총회가 끝나는 시각 이상 스트리밍이 끝나는 시각 이하의 시각에 채팅을 친 사람의 집합"의 교집합을 구하는 문제이다.

이를 가장 쉽게 구하는 방법 중 하나는 각각의 집합을 set을 이용해 구하고, 한 set에 들어있는 이름이 다른 set에도 들어있는지 하나하나 확인하는 것이다.

주어지는 각 시간은 문자열 상태로 그대로 두고 크기를 비교해도 실제 시각과 같은 비교 결과를 보이므로 특별한 가공 없이 그대로 사용해도 좋다.

같은 사람을 여러번 세는 경우가 없게끔 주의해 구현하자.

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

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

string A, B, C, X, Y;
set<string> st, st2;

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

	cin >> A >> B >> C;
	while (cin >> X >> Y) {
		if (X <= A) st.insert(Y);
		else if (B <= X && X <= C) {
			if (st.count(Y)) st2.insert(Y);
		}
	}
	cout << st2.size();
}

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

이번에 볼 문제는 백준 18004번 문제인 From A to B이다.
문제는 아래 링크를 확인하자.

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

\(a\)가 홀수인 경우에는 \(a\)에 1을 더하는 것 외에는 아무런 연산을 할 수 없다. \(a\)가 짝수인 경우를 생각해보자.

\(a\)가 \(b\)보다 작다면 \(a\)를 \(b\)로 만드는 과정중에 \(a\)를 2로 나누는 연산을 할 필요가 없음은 쉽게 관찰할 수 있다. \(a\)의 값이 증가하는 방법은 유일하므로 \(a\)를 감소시키는 연산을 사용해 얻을 수 있는 이득이 없기 때문이다.

\(a\)가 \(b\)보다 크다면 \(a\)를 2로 나누는 연산을 바로 하는 것이 항상 이득이 된다. \(a\)의 값은 언젠가 감소해야하므로 \(a\)를 2로 나누는 연산을 언젠가 적용해야 하는데, 값을 \(2k\)회 증가시키고 2로 나누는 연산을 적용해 얻을 수 있는 값은 2로 나누는 연산을 먼저 한 뒤 값을 \(k\)회 증가시켜 항상 얻을 수 있기 때문이다.

위 규칙에 따라 \(a\)를 \(b\)로 바꾸는 과정 중 \(a\)가 \(b\)보다 클 때의 과정을 시뮬레이션 돌려보는 코드를 작성해 문제를 해결하자. 그 뒤 \(a\)의 값을 1씩 증가시키는 횟수는 두 수의 차로 단순하게 계산할 수 있음을 확인하자. 또한 \(a\)를 2로 나누는 횟수는 많아야 32회밖에 없다는 것 또한 관찰하자.

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

#include <iostream>
using namespace std;

int A, B;
int cnt;

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

	cin >> A >> B;
	while (A > B) {
		if (A & 1) A++;
		else A /= 2;
		cnt++;
	}
	cout << cnt + B - A;
}

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

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

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

각 문자에 공이 떨어졌을 때 어떤 확률로 밑으로 떨어질지는 각 공의 움직임을 지문에 주어진 대로 시뮬레이션하는 것으로 알아낼 수 있다. 이 과정에서 주어진 문자열의 맨 왼쪽과 맨 오른쪽에 '.'을 하나씩 추가하고 그 사이의 문자들 각각에서 시뮬레이션을 시도하면 구현을 더 편하게 할 수 있다.

각 문자에 공이 떨어질 확률은 균등하므로 위에서 계산한 각 확률을 이용해 문제의 답을 구하자.

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

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

int N, val;
string s;

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

	cin >> s;
	while (s != "#") {
		N = s.length(), val = 0;
		s = "." + s + ".";
		for (int i = 1; i <= N; i++) {
			if (s[i] == '.') val += 2;
			else if (s[i] == '/') {
				int ii = i - 1;
				while (s[ii] == '_') ii--;
				if (s[ii] == '.') val += 2;
			}
			else if (s[i] == '\\') {
				int ii = i + 1;
				while (s[ii] == '_') ii++;
				if (s[ii] == '.') val += 2;
			}
			else if (s[i] == '|') {
				int ii;
				ii = i - 1;
				while (s[ii] == '_') ii--;
				if (s[ii] == '.') val++;
				ii = i + 1;
				while (s[ii] == '_') ii++;
				if (s[ii] == '.') val++;
			}
		}

		cout << val * 100 / (N * 2) << '\n';
		cin >> s;
	}
}

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

이번에 볼 문제는 백준 28858번 문제인 Пасьянс이다.
문제는 아래 링크를 확인하자.

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

먼저 홀수로 시작하는 수열 중 가장 긴 수열의 길이를 구해보자.

첫 홀수는 어떤 수로 골라야할까? 가장 긴 수열의 첫 항이 되는 홀수는 여러 가지 있을 수 있으나, 주어진 홀수 중 "가장 작은" 홀수로 시작하는 경우는 항상 포함되어 있다. 가장 작은 홀수로 시작하지 않는 수열이 있다면 그 수열의 첫 수를 가장 작은 홀수로 바꾸는 것으로 같은 길이의 수열을 얻을 수 있기 때문이다.

위와 같은 논리를 반복적으로 적용하면, 이 수열의 길이를 늘려나갈 때 앞서 나온 수보다 큰 수중 가장 작은 짝수와 홀수를 번갈아가면서 이어붙여나가는 것으로 구하고자 하는 수열 중 하나를 구할 수 있게 된다.

한편, 짝수로 시작하는 수열 중 가장 긴 수열의 길이도 이와 같은 방법으로 구할 수 있고, 두 길이 중 더 큰 값이 문제의 답이 될 것임을 어렵지 않게 관찰할 수 있다.

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

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

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

int N;
int A[100];
int oldX = -1000000007, oldY = -1000000006;
int cntX = 0, cntY = 0;

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N);
	
	for (int i = 0; i < N; i++) {
		if ((oldX + A[i]) & 1) oldX = A[i], cntX++;
		if ((oldY + A[i]) & 1) oldY = A[i], cntY++;
	}

	cout << max(cntX, cntY);
}

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

이번에 볼 문제는 백준 11811번 문제인 데스스타이다.
문제는 아래 링크를 확인하자.

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

두 양의 정수 \(a\)와 \(b\)에 대하여 \(a\&b\) (단, \(\&\)는 bitwise and 연산이다.)의 값을 \(k\)라 한다면 적어도 \(a\)와 \(b\)는 \(k\)에서 1로 나타나는 비트가 항상 1이어야 함을 알 수 있다. 이 성질을 이용하면 각 \(a_i\)와 \(a_j\)의, 1이어야 하는 최소한의 비트를 전부 구할 수 있다.

위에서 구한 비트가 문제의 답이 될 수 있음은 어렵지 않게 보일 수 있으므로 증명은 생략한다. (귀류법을 사용해보자.) 문제의 답이 유일하지 않을 수 있는 이유는 각 수에 다른 수에서 전혀 등장하지 않은 자릿수의 비트를 하나씩 끼워넣어도 문제의 답이 될 수 있기 때문이다.

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

#include <iostream>
using namespace std;

int N;
int A[1000];

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

	cin >> N;

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			int x; cin >> x;
			A[r] |= x, A[c] |= x;
		}
	}
	for (int i = 0; i < N; i++) cout << A[i] << ' ';
}