취미로 코딩하기

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

이번에 볼 문제는 백준 1262번 문제인 알파벳 다이아몬드이다.
문제는 아래 링크를 확인하자.

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

크기가 \(x\)인 다이아몬드로 격자를 채우면 각 행은 \(x\)행마다 반복되며 열 또한 \(x\)행마다 반복됨을 관찰하자.

따라서 \(r\)행(c\)열(0-based)의 문자는 \(r%x\)행\(c%x\)열의 문자와 같게 된다. 이 문자가 무엇인지를 계산해 문제를 해결하자. 크기가 \(x\)인 정사각형 격자에 적힌 문자는 격자의 중심으로부터 떨어진 각 칸의 맨해튼 거리와 관계 있음을 이용하면 계산을 빠르게 할 수 있다.

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

#include <iostream>
using namespace std;

int N, NN, RL, CL, RR, CR;

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

	cin >> N >> RL >> CL >> RR >> CR;
	NN = N * 2 - 1;
	N--;
	for (int r = RL; r <= RR; r++) {
		for (int c = CL; c <= CR; c++) {
			int rr = r % NN, cc = c % NN;
			int val = abs(rr - N) + abs(cc - N);
			if (val > N) cout << '.';
			else cout << (char)('a' + (val % 26));
		}
		cout << '\n';
	}
}

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

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

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

\(N\) 이하의 두 수 \(x\)와 \(y\)에 대하여 \(y\)가 \(x\)의 배수인 관계를 이루는 쌍\((x, y)\)의 개수는 \(O(\lg N)\)개만 존재한다는 점을 상기하자. (Harmonic Lemma)

위 관찰을 이용하면, 약수와 배수 관계를 갖는 모든 쌍에 대하여 두 수의 순서가 어떻게 되어있는지 일일이 세는 것으로도 문제를 충분히 해결할 수 있음을 알 수 있다.

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

#include <iostream>
using namespace std;

int N;
int A[100001];
int ans;

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		A[x] = i;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = i * 2; j <= N; j += i) {
			if (A[i] > A[j]) ans++;
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 27488번 문제인 Sum of Two Numbers이다.
문제는 아래 링크를 확인하자.

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

주어진 수의 각 자리는 항상 같거나 1 차이가 나는 두 수로 쪼갤 수 있음을 관찰하자.

이 쪼개진 두 수를 적절히 나누어 이어쓰면 합이 주어진 수와 같고 항상 각 자리에 적힌 숫자가 나타내는 수의 총합이 같거나 1 차이나는 두 수를 구할 수 있다.

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

#include <iostream>
using namespace std;

string s; int A, B;

void solve() {
	cin >> s; A = B = 0;
	int L = 0, R = 0;
	for (auto &l:s) {
		int x = l - '0', y = x;
		x /= 2; y -= x;
		if (L < R) {
			A = A * 10 + y, B = B * 10 + x;
			L += y, R += x;
		}
		else {
			A = A * 10 + x, B = B * 10 + y;
			L += x, R += y;
		}
	}
	cout << A << ' ' << B << '\n';
}

int T;

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

	cin >> T;
	while (T--) solve();
}

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

이번에 볼 문제는 백준 22128번 문제인 Молекула이다.
문제는 아래 링크를 확인하자.

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

흰색 돌끼리, 검은색 돌끼리 붙어 있으려면 어떤 돌에서 출발해 한 바퀴 돌아 같은 돌로 돌아올 때까지 돌의 색의 변화가 정확히 2회 있어야 하고 그 역도 성립함을 관찰하자. 또한, 주어진 연산으로는 돌의 색의 변화를 많아야 2회씩밖에 줄이지 못하고, 돌의 색의 변화가 2보다 큰 경우 한 번의 연산으로 변화 횟수를 항상 2회씩 줄일 수 있음을 관찰하자.

위 관찰을 이용하면 색이 다른 인접한 돌의 쌍의 개수를 세어 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int T, N;
string s;

void solve() {
	cin >> s; N = s.length(); s += s.front();
	int ans = -2;
	for (int i = 0; i < N; i++) {
		if (s[i] != s[i + 1]) ans++;
	}
	cout << ans / 2 << '\n';
}

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

	cin >> T;
	while (T--) solve();
}

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

이번에 볼 문제는 백준 23649번 문제인 Alice and Path이다.
문제는 아래 링크를 확인하자.

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

같은 행동을 6번 연속 하면 아무 행동도 하지 않은 것과 같게 됨을 관찰하자. 따라서, 주어진 행동을 마지막 행동부터 거꾸로 5번씩 실행하면 초기 상태로 항상 돌아갈 수 있다.

초기 상태로 돌아가면 위치 또한 처음과 똑같이 되고, 출력하는 문자열의 길이는 길어야 5만이므로 이와 같은 방법으로 문제를 충분히 해결할 수 있다.

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

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

string s;

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

	cin >> s;
	while (!s.empty()) {
		for (int k = 0; k < 5; k++) cout << s.back();
		s.pop_back();
	}
}

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

이번에 볼 문제는 백준 32315번 문제인 Cool Phone Numbers이다.
문제는 아래 링크를 확인하자.

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

구하고자 하는 값은 주어지는 전화번호 문자열을 구성하는 문자(단, '-' 제외)의 가짓수와 같다.

따라서, 주어진 문자열을 구성하는 문자들을 저장하는 set을 이용하면 문제를 단순하게 해결할 수 있다.

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

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

char c;
set<char> st;

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

	while (cin >> c) st.insert(c);
	cout << st.size() - 1;
}