취미로 코딩하기

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

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

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

주어진 유리수를 7진법으로 나타냈을 때의 소수점 아래 특정 자릿수를 구하는 문제이다.

10진수의 나눗셈 과정을 다시 생각해보자. 남은 분자에 10을 곱하고 분모로 분자를 나눈 몫을 자릿수로 나타낸 다음 분자의 값을 분모로 나눈 나머지로 바꾸는 것을 반복하는 것으로 문제를 해결할 수 있을 것이다.

7진수의 나눗셈 또한 위의 과정과 크게 다르지 않다. 다른 점은 분자에 곱하는 값이 10이 아닌 7이 되는 것 하나뿐이다. 이를 구현해 문제를 해결하자.

입력으로 주어지는 유리수는 가분수일 수 있으므로 첫 자리를 구하기 전에 분자를 분모로 나눈 나머지로 바꿔야 함에 유의하자.

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

#include <iostream>
using namespace std;

int T;
int A, B, L, R;

void solve() {
	A %= B;
	for (int i = 0; i <= R; i++) {
		A *= 7;
		int dgt = A / B; A %= B;
		if (L <= i) cout << dgt;
	}
	cout << '\n';
}

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

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> A >> B >> L >> R;
		cout << "Problem set " << t << ": " << A << " / " << B << ", base 7 digits " << L << " through " << R << ": ";
		solve();
	}
}

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

이번에 볼 문제는 백준 14515번 문제인 Yin and Yang Stones이다.
문제는 아래 링크를 확인하자.

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

주어진 두 연산 모두 항상 같은 개수의 흰 돌과 검은 돌을 제거함을 관찰하자. 따라서 연산을 어떤 순서로 몇번을 진행하는가에 관계없이 흰 돌의 개수와 검은 돌의 개수의 차는 일정하게 유지됨을 알 수 있다. 따라서 검은 돌과 흰 돌의 개수가 서로 다른 경우 문제의 답은 항상 0이 된다.

검은 돌과 흰 돌의 개수가 같다면 어떨까? 이 경우 한쪽 끝의 돌을 제외한 모든 돌을 고르면 항상 검은 돌과 흰 돌이 하나씩만 남음을 어렵지 않게 관찰할 수 있다. 따라서 검은 돌과 흰 돌의 개수가 서로 같은 경우 문제의 답은 항상 1이다.

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

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

#include <iostream>
using namespace std;

char c;
int cnt[128];

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

	while (cin >> c) cnt[c]++;
	if (cnt['W'] != cnt['B']) cout << 0;
	else cout << 1;
}

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

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

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

먼저 1번 방에서 \(N\)번 방까지 도달하기 위해 움직여야 하는 횟수가 상당히 많을 수 있음을 확인하자. 예를 들어 1번부터 50번 방까지로 이루어진 사이클 형태의 경로를 따라 한 바퀴 돌 때마다 에너지가 1씩 증가하고, 각각 에너지가 100씩 감소하는 51~99번 방을 거쳐 100번 방으로 도착해야 하는 형태의 그래프의 경우 거쳐야 하는 방의 수가 매우 많을 것이다. 이 문제는 한 실행에 여러 테스트케이스를 해결해야하므로, 위의 내용과 함께 생각해보면 도착할 때까지 직접 시뮬레이션을 돌리는 것은 적절한 풀이가 아닐 것이라고 결론내릴 수 있다.

위의 풀이가 비효율적인 이유는 위와 같이 사이클을 여러 번 돌아 \(N\)번 방에 도달하게 되는 경우 직접 사이클을 도는 시뮬레이션 과정이 오래 걸리기 때문이다. 이 사이클을 직접 따라 돌면서 \(N\)번 방까지 가는 과정을 무조건 살펴봐야 할까?

그렇지 않다. 이 문제에서는 \(N\)번 방의 도달 가능성만을 구하면 되므로, 사이클을 돌아야 하는 경우 \(1\)번 방에서 도달 가능하면서 에너지가 증가하는 사이클에 속한 각 방으로부터 \(N\)번 방으로 도달할 수 있는지를 확인하는 것으로 문제를 해결할 수 있다.

사이클을 돌아야 하는 경우와 그럴 필요가 없는 두 경우 모두에 신경써 문제를 해결하자.

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

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

int N, K;
int E[101];
vector<int> G[101], invG[101];
int HP[101], tmp[101], mxHP[101], oldmxHP[101];
int chk[101], visited[101], ans;

void dfs(int cur) {
	visited[cur] = 1;
	if (chk[cur]) ans = 1;
	for (auto &nxt:invG[cur]) {
		if (visited[nxt]) continue;
		dfs(nxt);
	}
}

void solve() {
	for (int i = 1; i <= N; i++) G[i].clear(), invG[i].clear();
	for (int i = 1; i <= N; i++) {
		cin >> E[i] >> K;
		G[i].clear();
		while (K--) {
			int x; cin >> x;
			G[i].emplace_back(x);
			invG[x].emplace_back(i);
		}
	}
	if (N == 1) {
		cout << "winnable\n";
		return;
	}

	memset(HP, 0xff, sizeof(HP));
	memset(mxHP, 0xff, sizeof(mxHP));
	HP[1] = mxHP[1] = 100;
	for (int k = 0; k < N; k++) {
		memset(tmp, 0xff, sizeof(tmp));
		for (int cur = 1; cur <= N; cur++) {
			if (HP[cur] < 0) continue;
			for (auto &nxt:G[cur]) {
				if (HP[cur] + E[nxt] < 1) continue;
				tmp[nxt] = max(tmp[nxt], HP[cur] + E[nxt]);
			}
		}
		swap(HP, tmp);
		if (HP[N] > 0) {
			cout << "winnable\n";
			return;
		}
		for (int i = 1; i <= N; i++) mxHP[i] = max(mxHP[i], HP[i]);
	}
	for (int i = 1; i <= N; i++) oldmxHP[i] = mxHP[i];
	for (int k = 0; k < N; k++) {
		memset(tmp, 0xff, sizeof(tmp));
		for (int cur = 1; cur <= N; cur++) {
			if (HP[cur] < 0) continue;
			for (auto &nxt:G[cur]) {
				if (HP[cur] + E[nxt] < 1) continue;
				tmp[nxt] = max(tmp[nxt], HP[cur] + E[nxt]);
			}
		}
		swap(HP, tmp);
		if (HP[N] > 0) {
			cout << "winnable\n";
			return;
		}
		for (int i = 1; i <= N; i++) mxHP[i] = max(mxHP[i], HP[i]);
	}
	memset(chk, 0, sizeof(chk));
	for (int i = 1; i <= N; i++) {
		if (mxHP[i] > oldmxHP[i]) chk[i] = 1;
	}
	memset(visited, 0, sizeof(visited)), ans = 0;
	dfs(N);
	if (ans) cout << "winnable\n";
	else cout << "hopeless\n";
}

int T;

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

	cin >> N;
	while (N > 0) {
		solve();
		cin >> N;
	}
}

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

이번에 볼 문제는 백준 23604번 문제인 Chinese Remainder Theorem이다.
문제는 아래 링크를 확인하자.

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

\(a_i\)와 \(b_i\)가 법 \(m\)에 대해 합동이라는 것은 \(m\)이 \(a_i\)와 \(b_i\)의 차의 약수라는 것과 동치임을 관찰하자.

따라서 모든 \(i\)에 대하여 \(a_i\)와 \(b_i\)가 법 \(m\)에 대해 합동이라는 것은 \(m\)이 모든 \(a_i\)와 \(b_i\)의 차의 약수라는 것과 같고, 이는 \(a_i\)와 \(b_i\)의 차들의 공약수와 같게 된다. 따라서 이 문제는 이러한 공약수들 중 가장 큰 수, 즉 최대공약수를 구하는 것으로 해결할 수 있다.

두 수의 최대공약수는 유클리드 호제법(Euclidean Algorithm)을 이용해 계산할 수 있다. 여러 수의 최대공약수는 둘씩 최대공약수를 구하는 것을 반복하는 것으로 구할 수 있다.

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

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

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

int N; ll ans;
ll A[100000], B;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	cin >> B; ans = abs(A[0] - B);
	for (int i = 1; i < N; i++) {
		cin >> B;
		ans = gcd(ans, abs(A[i] - B));
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 16481번 문제인 원 전문가 진우이다.
문제는 아래 링크를 확인하자.

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

삼각형의 내접원의 반지름은 (각 방접원의 반지름의 역수의 합)의 역수와 같다. 이를 이용해 간단한 사칙연산 코드를 작성하는 것으로 문제를 해결할 수 있다.

위 내용은 "루리에의 정리"라는 이름으로 잘 알려져있다. 증명이 궁금하다면 루리에의 정리를 검색해 자세한 내용을 알아보자.

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

#include <iostream>
using namespace std;
typedef long double ld;

ld A, B, C;

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

	cin >> A >> B >> C;
	cout << fixed;
	cout.precision(10);
	cout << 1 / (1 / A + 1 / B + 1 / C);
}

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

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

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

주어진 상을 규칙에 따라 움직여 왕이 위치한 곳으로 옮길 때 그 움직인 횟수의 최솟값을 구하는 문제이다.

각 칸을 노드로, 어떤 칸에서 다른 칸으로 움직일 수 있는 관계를 (가중치가 없고 방향이 있는) 에지로 나타내면 주어진 문제는 가중치 없는 방향그래프에서의 최단거리 문제로 표현할 수 있다. 이는 BFS를 통해 해결할 수 있다.

상의 움직임과 체스의 나이트의 움직임이 유사하게 느껴질 수 있지만,

상은 문제에 주어진 그림과 같이 움직이는 점선 위에 다른 말이 놓여있을 경우 그 점선을 따라 진행하는 움직임을 할 수 없다는 점(즉, 다른 말을 뛰어넘을 수 없다는 점)이 다르므로 이에 유의해 구현하자. 특히 왕 또한 (상이 아닌) 다른 말에 해당한다는 점을 잊지 말자.

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

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

int sR, sC, eR, eC;
int dist[10][9];
queue<pair<int, int>> que;
int dr[8] = {3,2,-2,-3,-3,-2,2,3};
int dc[8] = {2,3,3,2,-2,-3,-3,-2};
vector<pair<int, int>> chk[8];

void bfs() {
	que.push(make_pair(sR, sC));
	dist[sR][sC] = 1;
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 8; i++) {
			bool overing = 0;
			for (auto &p:chk[i]) {
				int rr = r + p.first, cc = c + p.second;
				if (rr < 0 || rr > 9 || cc < 0 || cc > 8 || (rr == eR && cc == eC)) overing = 1;
			}
			if (overing) continue;
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr > 9 || cc < 0 || cc > 8 || dist[rr][cc]) continue;
			dist[rr][cc] = dist[r][c] + 1;
			que.push(make_pair(rr, cc));
		}
	}
}

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

	chk[0].emplace_back(make_pair(1,0));
	chk[0].emplace_back(make_pair(2,1));
	chk[1].emplace_back(make_pair(0,1));
	chk[1].emplace_back(make_pair(1,2));
	chk[2].emplace_back(make_pair(0,1));
	chk[2].emplace_back(make_pair(-1,2));
	chk[3].emplace_back(make_pair(-1,0));
	chk[3].emplace_back(make_pair(-2,1));
	chk[4].emplace_back(make_pair(-1,0));
	chk[4].emplace_back(make_pair(-2,-1));
	chk[5].emplace_back(make_pair(0,-1));
	chk[5].emplace_back(make_pair(-1,-2));
	chk[6].emplace_back(make_pair(0,-1));
	chk[6].emplace_back(make_pair(1,-2));
	chk[7].emplace_back(make_pair(1,0));
	chk[7].emplace_back(make_pair(2,-1));

	cin >> sR >> sC >> eR >> eC;
	bfs();

	cout << dist[eR][eC] - 1;
}