취미로 코딩하기

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

이번에 볼 문제는 백준 14244번 문제인 트리 만들기이다.
문제는 아래 링크를 확인하자.

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

\(n\)이 3 이상인 트리에는 항상 degree가 2 이상인 노드(즉, 리프가 아닌 노드)가 존재한다. 따라서 0번 노드가 리프가 아니라고 가정해도 문제의 조건을 만족하는 트리를 항상 찾을 수 있다.

이제 1번부터 \(m\)번 노드를 각각 0번 노드와 연결해 리프로 삼고, \(m+1\)번 이상 번호의 노드는 기존 리프노드와 연결하는 것으로 총 리프의 수를 유지하면 문제의 조건을 만족하는 트리를 항상 얻을 수 있다. 주어진 조건에 따라 \(m\)은 \(n-1\) 이하이므로 위와 같은 트리 구성이 항상 가능함을 확인하자.

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

#include <iostream>
using namespace std;

int N, M;

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

	cin >> N >> M;
	for (int m = 1; m <= M; m++) cout << 0 << ' ' << m << '\n';
	for (int i = M + 1; i < N; i++) cout << i - 1 << ' ' << i << '\n';
}

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

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

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

먼저 다음과 같은 사전지식을 상기하자:
\(O(\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n}) = O(n\lg n)\) (조화급수 형태로 나타나는 알고리즘의 시간복잡도 계산)

두 양의 정수 \(a\), \(b\)에 대하여 어떤 양의 정수 \(c\)가 존재해 \(a^2+b=c^2\)가 성립한다면 이는 곧 \(b = (c-a)(c+a)\)가 성립한다는 것을 의미한다. 따라서 주어진 \(n\) 이하의 각 정수 \(a_j\)에 대하여 위와 같은 형태로 분해할 수 있는지를 판단하는 것으로 문제를 해결할 수 있다.

한편 위의 사전지식에 의하여, 1 이상 100만 이하의 각 정수 \(k\)에 대해 모든 100만 이하의 \(k\)의 배수마다 (해당 수를 \(k\)로 나눈 수)와 \(k\) 각 수를 쪼개는 시도를 반복하는 것은 제한시간 내에 충분히 해낼 수 있음을 알 수 있다. 이를 활용해 \(b\)를 쪼갤 수 있는 모든 방법을 직접 시도해 문제의 답을 구하자.

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

#include <iostream>
using namespace std;

int N;
bool A[1000001];
int ans;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		A[x] = 1;
	}

	for (int i = 1; i < 1000001; i++) {
		for (int j = i; j < 1000001; j += i) {
			if (!A[j]) continue;
			int AA = i, BB = j / i;
			if (AA > BB) continue;
			int K = BB - AA;
			if (K & 1) continue;
			K >>= 1;
			if (A[K] && K != j) ans++;
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 16894번 문제인 약수 게임이다.
문제는 아래 링크를 확인하자.

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

"더 이상 적을 수가 없는 사람이 게임을 이긴다"는 조건을 꼭 확인하자. 더 이상 적을 수가 없는 사람이 지는 것이 아니다!

주어진 수 \(N\)이 1이거나 소수인 경우 어떤 수도 더 적을 수 없으므로 선공이 게임을 항상 이긴다. 한편 \(N\)이 두 소수(서로 다를 필요는 없다) \(p\)와 \(q\)의 곱 \(pq\)로 표현되는 경우, 다음으로 적을 수 있는 수 \(p\)와 \(q\)가 존재하고 그 중 어떤 수를 적더라도 상대는 더 이상 적을 수가 없으므로 후공이 게임을 항상 이긴다.

위에 해당하는 수가 아닌 다른 수의 경우, 해당 수는 항상 두 소수의 곱의 꼴로 나타낼 수 있는 약수가 존재하므로 해당 수를 적어내는 것으로 선공이 항상 이길 수 있다.

위의 내용을 구현해 문제를 해결하자. 이를 위해서는 \(N\)을 소인수분해할 필요가 있는데, 이는 \(O(\sqrt{N})\)회의 나눗셈 시도로 해낼 수 있다. 이 방법은 주어진 제한에서 충분히 사용할 수 있을 정도로 빠른 방법이다.

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

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

ll N;
vector<ll> vec;

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

	cin >> N;
	for (ll i = 2; i * i <= N; i++) {
		while (!(N % i)) N /= i, vec.emplace_back(i);
	}

	if (N > 1) vec.emplace_back(N);

	if (vec.size() == 2) cout << "cubelover";
	else cout << "koosaga";
}

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

이번에 볼 문제는 백준 27505번 문제인 천국의 계단이다.
문제는 아래 링크를 확인하자.

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

높이가 \(A\)인 직육면체와 \(B\)인 직육면체로 만들 수 있는 모든 높이의 가짓수를 구할 수 있다면 \(N\)에서 해당 가짓수를 빼는 것으로 문제를 해결할 수 있다. 만들 수 있는 모든 높이의 가짓수를 구해보자.

먼저 \(A\)와 \(B\)가 서로소라고 가정해 보자. 어떤 높이가 \(H\)인 어떤 단이 높이가 \(B\)인 직육면체를 \(A\)개 이상 사용해 만들어진다면 높이 \(H\)인 단은 높이 \(B\)인 직육면체 \(A\)개를 높이 \(A\)인 직육면체 \(B\)개로 바꿔서 만들 수도 있음을 관찰하자. 즉, 어떤 높이 \(H\)인 단이 만들어질 수 있다면 높이 \(B\)의 직육면체를 \(A\)개 미만으로 사용해 항상 만들 수 있음을 알 수 있다. 주어지는 \(A\)와 \(B\)의 크기가 충분히 작으므로(1천만 이하), 높이가 \(B\)인 직육면체를 0개, 1개, ..., \(A-1\)개 사용해 만들 수 있는 단의 높이의 개수를 각각 구해 더하는 것으로 필요한 값을 구할 수 있다.

\(A\)와 \(B\)가 서로소가 아니라면 어떨까? 이 경우 \(B\)의 배수가 가장 빠르게 \(A\)의 배수가 되는 경우는 \(B\)에 \(A/\gcd (A,B)\)를 곱했을 때가 됨은 쉽게 관찰할 수 있다. 이를 활용해 이 경우 또한 \(A\)와 \(B\)가 서로소인 경우와 같은 방법으로 문제를 해결할 수 있다.

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

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

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

ll N, A, B, AA, G;
ll cnt;

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

	cin >> N >> A >> B;
	G = gcd(A, B);
	AA = A / G;
	for (ll b = 0; b < AA; b++) {
		ll K = N - B * b;
		if (K < 0) break;
		cnt += K / A + 1;
	}

	cout << N - cnt + 1;
}

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

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

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

"와우매직"을 적용하지 않은 정수들은 서로 약수와 배수 관계에 있어야 함을 관찰하자. 그리고 "와우매직"을 적용할 때 각 미네랄 성분의 함량을 일괄적으로 1로 바꾼다면 항상 다른 모든 수와 약수와 배수 관계에 있게 됨을 관찰하자. 이와 같은 관찰에 따라 이 문제는 "서로 약수와 배수 관계에 있는 maximal한 집합"을 찾아 그 원소의 개수를 \(N\)에서 뺀 값을 구하는 것으로 해결할 수 있음을 알 수 있다.

한편, 어떤 주어진 정수들이 모든 쌍이 서로 약수와 배수의 관계를 이룬다면 해당 정수들을 오름차순으로 나열했을 때 먼저 등장하는 수는 항상 뒤에 등장하는 수의 약수가 되어야 함을 관찰하자. 이와 같은 관찰을 이용하면, 주어지는 \(N\)개의 수를 오름차순으로 정렬한 다음 '다음 항이 항상 이전 항의 배수인 부분수열'의 길이의 최댓값을 구하는 것으로 원하는 수의 집합을 구할 수 있음을 알 수 있다. 그 크기는 \(O(N^2)\) DP로 어렵지 않게 구할 수 있다.

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

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

int N;
int A[5000];
int dp[5000], mx;

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++) {
		mx = max(mx, dp[i]);
		for (int j = i + 1; j < N; j++) {
			if (A[j] % A[i]) continue;
			dp[j] = max(dp[j], dp[i] + 1);
		}
	}

	cout << N - (mx + 1);
}

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

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

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

이번 턴에 건드려야 하는 block stack의 block 개수를 \(A\), 다른 block stack의 block 개수를 \(B\)라 하자. \(A\)가 \(B\)의 배수이면 이번 턴에 block을 조작하는 사람이 이김은 자명하다. 만약 \(A > 2B\)가 성립한다면 이번 턴에 block을 조작하는 사람은 다음으로 조작하게 될(즉, 이번 턴에 조작해야 하는 block stack이 아닌 다른) block stack을 자신이 처음으로 조작할지 상대가 먼저 조작하게 할지 마음대로 결정할 수 있다. 위와 같은 경우들은 이번 턴에 조작하는 사람이 항상 이기게 된다.

위의 경우를 제외하면 남는 경우는 \(B<A<2B\)인 경우인데, 이 때 가능한 유일한 행동은 현재의 block stack에서 \(B\)개의 block을 제거하고 턴을 넘기는 것임을 관찰하자. 이 경우 승패는 다음 턴에 따라 결정된다.

위 과정은 여러 번 반복될 수 있으나, 반복할 때마다 \(A\)의 크기는 절반 미만으로 줄어들어 반복 횟수가 \(O(lg(A) + lg(B))\)밖에 안 되므로 이와 같은 과정을 시뮬레이션하는 것으로 문제를 충분히 해결할 수 있다.

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

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

ll A, B;
int ans;

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

	cin >> A >> B;
	if (A < B) swap(A, B);
	while (B < A && A < B * 2) {
		ans ^= 1;
		A -= B;
		swap(A, B);
	}

	if (ans) cout << "lose";
	else cout << "win";
}