취미로 코딩하기

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

이번에 볼 문제는 백준 6511번 문제인 Black and white painting이다.
문제는 아래 링크를 확인하자.

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

어떤 칸이 조건을 만족하는 체스판의 우하단 칸이 될 수 있다는 것은 (1) 해당 위쪽과 왼쪽으로 적어도 7칸씩이 더 있으며 (2) 해당 칸의 색이 흰색이어야 한다는 것과 필요충분조건이 됨을 관찰하자.

(1)을 만족하는 칸은 주어지는 그림의 위쪽 7열과 왼쪽 7열을 제외한 모든 칸과 같다. 이 칸들은 직사각형의 형태를 이루고 있으므로, 남은 칸의 개수가 짝수개이면 그중 절반이 흰색 칸이 됨을 어렵지 않게 관찰할 수 있다. 또한 남은 칸의 개수가 홀수개인 경우 가장 오른쪽 아래 칸을 제외한 칸의 절반이 흰색 칸이 됨을 관찰할 수 있다.

위와 같은 관찰을 이용해 문제를 해결하는 코드를 작성하자.

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

#include <iostream>
using namespace std;

int R, C, K;

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

	cin >> R >> C >> K;
	while (R || C || K) {
		int val = (R - 7) * (C - 7);
		if (val & 1) cout << val / 2 + K << '\n';
		else cout << val / 2 << '\n';
		cin >> R >> C >> K;
	}
}

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

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

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

창석이가 공을 하나 던질 때마다 경기가 어떻게 진행되는지를 직접 시뮬레이션하는 코드를 작성해 문제를 해결하자.

이 시뮬레이션의 구현을 위해 1루, 2루 및 3루에 주자가 있는지를 저장해둘 변수, 현재 누적되어 있는 '볼'의 개수를 저장할 변수 및 지금까지 실점한 점수를 기록할 변수를 만들자. 그리고 지문에 주어진 규칙에 맞추어 위 변수들을 적절히 변경해 문제를 해결하자.

폭투를 던지면서 총 '볼'의 개수가 4개가 되었을 때 일어나는 상황을 유의해 구현하자.

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

#include <iostream>
using namespace std;

int Q;
int base1, base2, base3;
int cnt, ans;

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

	cin >> Q;
	while (Q--) {
		int x; cin >> x;
		if (x == 1) cnt++;
		else if (x == 2) cnt = 4;
		else {
			cnt++;
			if (base3) base3 = 0, ans++;
			if (base2) base2 = 0, base3 = 1;
			if (base1) base1 = 0, base2 = 1;
		}
		if (cnt == 4) {
			cnt = 0;
			if (base1) {
				if (base2) {
					if (base3) {
						base3 = 0, ans++;
					}
					base2 = 0, base3 = 1;
				}
				base1 = 0, base2 = 1;
			}
			base1 = 1;
		}
	}

	cout << ans;
}

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

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

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

0/1과 1/1, 그리고 \(N\) 이하의 분모를 갖는 모든 기약분수를 크기순으로 나열하는 문제이다.

이에 해당하는 기약분수의 수는 충분히 적으므로, 모든 기약분수를 벡터에 저장한 후 각 기약분수를 크기순으로 정렬해 문제를 해결할 수 있다. 각 분수가 기약분수인지 판정하는 것은 유클리드 호제법을 이용해 어렵지 않게 해낼 수 있다.

이 과정에서 분수의 대소 비교는 실수값으로 해도 좋지만 두 분모의 공배수를 두 분수에 곱해도 대소관계가 변하지 않음을 이용하면 정수의 비교로도 오차 없이 구현할 수 있다.

이 문제에서 출력해야 하는 수열의 성질을 더 깊이 알아보고 싶다면 Farey Sequence와 Stern-Brocot Tree에 대해 조사해보는 것을 추천한다.

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

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

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

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

int N;
vector<pair<int, int>> vec;

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

	cin >> N;
	vec.emplace_back(make_pair(0, 1));
	vec.emplace_back(make_pair(1, 1));
	for (int n = 2; n <= N; n++) {
		for (int m = 1; m < n; m++) {
			if (gcd(n, m) > 1) continue;
			vec.emplace_back(make_pair(m, n));
		}
	}

	sort(vec.begin(), vec.end(), comp);
	cout << vec.size() << '\n';
	for (auto &p : vec) cout << p.first << '/' << p.second << '\n';
}

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

이번에 볼 문제는 백준 12971번 문제인 APC는 쉬운 난이도 순일까, 아닐까?이다.
문제는 아래 링크를 확인하자.

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

주어진 순서대로의 문제들의 배열을 A, 난이도 순서대로 정렬된 문제들의 배열을 B라 하자. 이때 A와 B가 같다면 문제의 답은 OK가 될 것이고 그렇지 않다면 KO가 될 것임은 자명하다. 한편 문제의 조건에 따라 A와 B에서 차례가 서로 다른 문제가 정확히 한 쌍 존재하므로 답이 KO인 경우 A와 B를 살펴 문제를 해결할 수 있다.

문제의 배열을 정렬해 문제를 해결하자. 정렬에 사용할 비교 기준을 구현할 때 B, S, G, P, D의 순서는 자연스러운 비교가 어려우므로 이에 신경써 구현하자. 또한 수를 문자열의 상태로 두고 비교하면 이 문제에서 필요한 대소비교가 되지 않는다는 점에도 유의하자.

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

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

int N;
pair<int, int> A[1000], B[1000];
vector<int> ans;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		int X, Y;
		if (s.front() == 'B') X = 1;
		else if (s.front() == 'S') X = 2;
		else if (s.front() == 'G') X = 3;
		else if (s.front() == 'P') X = 4;
		else X = 5;
		Y = stoi(s.substr(1, s.length() - 1));
		A[i] = B[i] = make_pair(X, -Y);
	}

	sort(B, B + N);
	for (int i = 0; i < N; i++) {
		if (A[i] != B[i]) ans.emplace_back(i);
	}
	if (ans.empty()) cout << "OK";
	else {
		cout << "KO\n";
		int x = B[ans.front()].first;
		if (x == 1) cout << 'B';
		else if (x == 2) cout << 'S';
		else if (x == 3) cout << 'G';
		else if (x == 4) cout << 'P';
		else cout << 'D';
		cout << -B[ans.front()].second << ' ';

		x = B[ans.back()].first;
		if (x == 1) cout << 'B';
		else if (x == 2) cout << 'S';
		else if (x == 3) cout << 'G';
		else if (x == 4) cout << 'P';
		else cout << 'D';
		cout << -B[ans.back()].second << ' ';
	}
}

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

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

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

어떤 \(P_1\),  \(P_2\),  \(P_3\)로 나눈 나머지가 각각 \(X_1\),  \(X_2\),  \(X_3\)인 수 \(N\)이 존재한다고 가정해보자. 이때 \(N\)이 \(P_1P_2P_3\)보다 크다면 \(N-P_1P_2P_3\) 또한 위의 성질을 만족함을 쉽게 알 수 있다. 따라서 문제의 답이 존재한다면 1부터 \(P_1P_2P_3\)까지의 수중에서 항상 찾을 수 있고, 여기에서 답을 찾지 못했다면 -1을 출력해 문제를 해결할 수 있다.

문제의 제약조건에 따라 \(P_1P_2P_3\)은 2700만 이하이므로 1부터 \(P_1P_2P_3\)까지의 정수를 하나하나 확인하는 브루트포스로 이 문제를 충분히 빠르게(2초 이내로) 해결할 수 있다.

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

#include <iostream>
using namespace std;

int P1, P2, P3, X1, X2, X3;

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

	cin >> P1 >> P2 >> P3 >> X1 >> X2 >> X3;
	for (int i = 1; i < 30000000; i++) {
		if (i % P1 != X1) continue;
		if (i % P2 != X2) continue;
		if (i % P3 != X3) continue;
		cout << i;
		return 0;
	}
	cout << -1;
}

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

이번에 볼 문제는 백준 13728번 문제인 행렬식과 GCD이다.
문제는 아래 링크를 확인하자.

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

먼저 주어진 형태의 \(n\)행 \(n\)열(\(n>2)\) tridiagonal matrix의 determinant \(D_n\)를 구하는 점화식을 유도해보자. 이 점화식은 먼저 우하단 원소를 기준으로 행방향으로 여인수 전개(Cofactor Expansion)을 하고, 그 다음으로 \(n-1\)행 \(n-1\)열 행렬꼴이 아닌 다른 행렬을 우하단 원소를 기준으로 열방향으로 여인수 전개하는 것으로 구할 수 있다. 구체적으로, 다음과 같은 점화식을 얻는다:

\(D_n = D_{n-1}+D_{n-2}\)

한편 \(D_1=1\), \(D_2=2\)임은 어렵지 않게 계산할 수 있다. 따라서 \(D_n=F_{n+1}\)이 성립한다. 여기서 \(F_n\)은 \(n\)번째 피보나치 수이다.

한편, \(\gcd(F_i,F_j)=F_{\gcd(i,j)}\)임은 well-known 지식이다. 이를 활용해 \(n+1\)번째까지의 피보나치 수(를 1000000007로 나눴을 때의 나머지)를 미리 구해두고 각 최대공약수번째 수를 하나하나 직접 더해 문제를 해결하자.

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

#include <iostream>
using namespace std;

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

int F[100002];
int N, ans;

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

	F[1] = 1;
	for (int i = 2; i < 100002; i++) {
		F[i] = F[i - 1] + F[i - 2];
		if (F[i] > 1000000006) F[i] -= 1000000007;
	}
	cin >> N; N++;
	for (int i = 2; i <= N; i++) {
		int g = gcd(i, N);
		ans += F[g];
		if (ans > 1000000006) ans -= 1000000007;
	}

	cout << ans;
}