취미로 코딩하기

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

이번에 볼 문제는 백준 27261번 문제인 Номера по диагонали이다.
문제는 아래 링크를 확인하자.

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

R행 C열의 칸을 문제에서 주어진 규칙과 같이 채워나갈 때 각 주어지는 수가 쓰여진 칸의 행과 열을 각각 출력하는 문제이다.

R이 C보다 작다고 가정해보자. 이 때, 좌상단의 R(R-1)/2까지의 수와 우하단의 RC-R(R-1)/2를 초과하는 수들을 제외한 남은 수들은 매우 규칙적인 배열을 하고 있음을 관찰할 수 있다. 또한, 좌상단 또는 우하단에 있는 수들의 위치는 각 수가 몇 번째 대각선에 있는지를 이진탐색 등을 이용해 알아내는 것으로 빠르게 구해낼 수 있음을 관찰할 수 있다.

마찬가지로 R이 C보다 큰 경우에도 칸에 적힌 수들의 규칙을 유사하게 분석할 수 있음을 관찰할 수 있다. 이와 같은 관찰과 같이 경우를 나누어 문제의 답을 찾는 코드를 작성하자.

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

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

ll R, C, Q;

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

	cin >> R >> C >> Q;
	
	if (R < C) {
		while (Q--) {
			ll X; cin >> X;
			if (X <= R * (R - 1) / 2) {
				ll dL = 1, dR = R - 1;
				while (dL < dR) {
					ll mid = (dL + dR) / 2;
					if (X <= mid * (mid + 1) / 2) dR = mid;
					else dL = mid + 1;
				}
				cout << X - dL * (dL - 1) / 2 << ' ' << (dL + 1) - (X - dL * (dL - 1) / 2) << '\n';
			}
			else if (X > R * C - R * (R - 1) / 2) {
				X = R * C - X + 1;
				ll dL = 1, dR = R - 1;
				while (dL < dR) {
					ll mid = (dL + dR) / 2;
					if (X <= mid * (mid + 1) / 2) dR = mid;
					else dL = mid + 1;
				}
				cout << (R + 1) - (X - dL * (dL - 1) / 2) << ' ' << (C + 1) - ((dL + 1) - (X - dL * (dL - 1) / 2)) << '\n';
			}
			else {
				ll D = (X - R * (R - 1) / 2 - 1) / R;
				cout << (X - R * (R - 1) / 2 - 1) % R + 1 << ' ' << R - ((X - R * (R - 1) / 2 - 1) % R) + D << '\n';
			}
		}
	}
	else {
		while (Q--) {
			ll X; cin >> X;
			if (X <= C * (C - 1) / 2) {
				ll dL = 1, dR = C - 1;
				while (dL < dR) {
					ll mid = (dL + dR) / 2;
					if (X <= mid * (mid + 1) / 2) dR = mid;
					else dL = mid + 1;
				}
				cout << X - dL * (dL - 1) / 2 << ' ' << (dL + 1) - (X - dL * (dL - 1) / 2) << '\n';
			}
			else if (X > R * C - C * (C - 1) / 2) {
				X = R * C - X + 1;
				ll dL = 1, dR = C - 1;
				while (dL < dR) {
					ll mid = (dL + dR) / 2;
					if (X <= mid * (mid + 1) / 2) dR = mid;
					else dL = mid + 1;
				}
				cout << (R + 1) - (X - dL * (dL - 1) / 2) << ' ' << (C + 1) - ((dL + 1) - (X - dL * (dL - 1) / 2)) << '\n';
			}
			else {
				ll D = (X - C * (C - 1) / 2 - 1) / C;
				cout << (X - C * (C - 1) / 2 - 1) % C + D + 1 << ' ' << C - (X - C * (C - 1) / 2 - 1) % C << '\n';
			}
		}
	}
}

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

이번에 볼 문제는 백준 27258번 문제인 Дроби이다.
문제는 아래 링크를 확인하자.

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

분모가 n 이하인 모든 분수에 대하여 1/p와 1/q 사이에 있는 모든 기약분수를 찾는 것은 모든 가능한 분모와 분자의 쌍에 대해 조사(브루트포스)하는 것으로 해낼 수 있다.

이와 같이 얻은 기약분수들을 크기순으로 정렬해 문제를 해결하자. 기약분수를 두 정수의 순서쌍으로 저장하고, a/b < c/d의 대소관계식을 ad < bc와 같은 정수의 연산으로 구현하면 오차에 구애받지 않고 문제를 해결할 수 있다.

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

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

int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

int N, P, Q;
vector<pair<int, int>> fracs;

bool comp(pair<int, int>& p1, pair<int, int>& p2) {
	return p1.second * p2.first < p1.first* p2.second;
}

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

	cin >> N >> P >> Q;
	for (int n = 1; n <= N; n++) {
		for (int m = 1; m <= N; m++) {
			if (gcd(n, m) == 1 && n < m * P && m * Q < n) fracs.emplace_back(make_pair(n, m));
		}
	}

	sort(fracs.begin(), fracs.end(), comp);

	for (auto& p : fracs) cout << p.second << '/' << p.first << '\n';
}

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

이번에 볼 문제는 백준 27260번 문제인 Красивые перестановки이다.
문제는 아래 링크를 확인하자.

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

1부터 N까지로 구성된 모든 순열에 대하여 인접한 두 원소의 곱의 합이 k의 배수인지를 확인하는 문제이다.

가능한 모든 순열을 생성하는 코드를 작성해 문제를 해결하자.

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

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

int N, K;
bool visited[11];
vector<int> vec;
int val, ans;

void func(int cnt) {
	if (cnt == N) {
		if (val % K == 0) ans++;
	}
	else {
		for (int i = 1; i <= N; i++) {
			if (visited[i]) continue;
			val += vec.back() * i;
			visited[i] = 1;
			vec.emplace_back(i);
			func(cnt + 1);
			vec.pop_back();
			visited[i] = 0;
			val -= vec.back() * i;
		}
	}
}

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

	cin >> N >> K;

	for (int n = 1; n <= N; n++) {
		visited[n] = 1;
		vec.emplace_back(n);
		func(1);
		vec.pop_back();
		visited[n] = 0;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 27259번 문제인 Разноцветные диагонали이다.
문제는 아래 링크를 확인하자.

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

NxN 격자판의 각 칸에 대하여 그 칸에서 두 대각선까지의 각 거리 중 작은 값을 구할 수 있다면 해당 칸에 인쇄될 색을 계산해 문제를 간단히 해결할 수 있다.

어떤 칸에서 한 대각선까지의 거리는 그 칸에서 대각선까지 일직선으로 도달하기까지 필요한 칸 수와 같다는 점을 관찰해 식을 세워 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;

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 d1 = abs(r - c), d2 = abs(r + c - (N - 1));
			cout << (char)('a' + min(d1, d2) % 26);
		}
		cout << '\n';
	}
}

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

이번에 볼 문제는 백준 27257번 문제인 Любитель нулей이다.
문제는 아래 링크를 확인하자.

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

주어진 양의 정수를 읽어 그 수의 leading zero와 trailing zero를 제외한 10진표현의 '0'의 개수를 세는 문제이다.

양의 정수를 10으로 나눈 나머지와 해당 수의 일의 자리가 같음을 이용해 수를 10으로 나누는 것을 반복하면서 각 자리를 확인해 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N, ans;

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

	cin >> N;
	while (N % 10 == 0) N /= 10;
	while (N) {
		if (N % 10 == 0) ans++;
		N /= 10;
	}

	cout << ans;
}