취미로 코딩하기

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

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

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

"두 점 사이의 Manhattan Distance와 Euclidean Distance가 같다"는 것은 "두 점의 \(x\)좌표가 서로 같거나 \(y\)좌표가 서로 같다"는 것과 동치임을 어렵지 않게 증명할 수 있다.

이를 이용하면, 문제에서 구하는 값은 \(x\)좌표 또는 \(y\)좌표가 서로 일치하는 점의 쌍의 수를 세는 것으로 해결할 수 있다. 글쓴이는 앞서 나온 점들 중 \(x\)좌표가 같은 점의 개수와 \(y\)좌표가 같은 점의 개수를 각각 기록해 문제를 해결했다. 이 과정에서 좌표가 일치하는 두 점의 경우 두 경우 모두에 포함되어 두 번씩 계수되므로 이에 유의하여 구현하자.

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

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

int N;
map<int, int> mpx, mpy;
map<pair<int, int>, int> mp;
ll ans;

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

	cin >> N;
	while (N--) {
		int x, y; cin >> x >> y;
		ans += mpx[x];
		ans += mpy[y];
		ans -= mp[make_pair(x, y)];
		mpx[x]++, mpy[y]++, mp[make_pair(x, y)]++;
	}
	cout << ans;
}

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

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

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

각 층에 대하여, 주어진 상황은 "101"과 "010"은 그런디 수가 0, (맨 윗층을 제외한)"111"은 그런디 수가 2, 나머지는 그런디 수가 1인 돌무더기인 님(Nim) 게임으로 생각할 수 있음을 관찰하자.

이를 이용하면 스프라그-그런디 정리(Sprague-Grundy Theorem)을 활용해 문제를 간단히 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N;
int val;

void solve() {
	val = 2;
	cin >> N;
	while (N--) {
		int cnt = 0;
		char x, y, z; cin >> x >> y >> z;
		if (x == '1' && y == '0' && z == '1') continue;
		if (x == '1') cnt++;
		if (y == '1') cnt++;
		if (z == '1') cnt++;
		val ^= (cnt - 1);
	}
	if (val) cout << "Yesyes\n";
	else cout << "Nono\n";
}

int T;

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

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

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

이번에 볼 문제는 백준 12051번 문제인 Dynamic Grid (Large)이다.
문제는 아래 링크를 확인하자.

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

주어지는 격자의 칸의 수가 10000 이하이고, 서로 연결된 칸의 쌍의 개수는 40000 이하이고, connected region의 수를 세야 하는 횟수는 많아야 10000회임을 관찰하자. 따라서 제한시간이 5초로 널널함을 이용하면, connected region의 수를 구하는 쿼리가 주어질 때마다 매번 격자 전체를 살펴도 문제를 충분히 해결할 수 있음을 관찰할 수 있다.

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

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

int R, C, Q;
char board[100][100];
int visited[100][100];
queue<pair<int, int>> que;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void bfs() {
	int ans = 0;
	memset(visited, 0, sizeof(visited));
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == '1' && !visited[r][c]) {
				que.push(make_pair(r, c));
				visited[r][c] = 1;
				while (!que.empty()) {
					int rr = que.front().first, cc = que.front().second; que.pop();
					for (int i = 0; i < 4; i++) {
						int rrr = rr + dr[i], ccc = cc + dc[i];
						if (rrr < 0 || rrr >= R || ccc < 0 || ccc >= C || board[rrr][ccc] == '0' || visited[rrr][ccc]) continue;
						visited[rrr][ccc] = 1;
						que.push(make_pair(rrr, ccc));
					}
				}
				ans++;
			}
		}
	}
	cout << ans << '\n';
}

void solve() {
	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
		}
	}
	cin >> Q;
	while (Q--) {
		char q; cin >> q;
		if (q == 'Q') bfs();
		else {
			int r, c; char x; cin >> r >> c >> x;
			board[r][c] = x;
		}
	}
}

int T;

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

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ":\n";
		solve();
	}
}

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

이번에 볼 문제는 백준 26091번 문제인 현대모비스 소프트웨어 아카데미이다.
문제는 아래 링크를 확인하자.

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

주어진 학회원들로 \(K\)팀을 구성할 수 있는 상황을 생각해보자. 만약 능력치가 가장 높은 \(K\)명 중 어떤 사람이 \(K\)팀 구성에 포함되어 있지 않은 경우 그보다 작은 능력치를 가진 두 명으로 구성된 팀이 항상 존재하며, 해당 팀의 한 사람을 능력치가 높은 사람으로 교체해도 \(K\)팀을 항상 구성할 수 있음을 알 수 있다. 따라서 \(K\)팀을 구성할 수 있다면 능력치가 가장 높은 \(K\)명이 모두 포함된 팀 구성이 항상 존재함을 알 수 있다.

비슷한 방법으로, 어떤 \(2K\)명을 이용한 팀 구성이 존재할 경우 능력치가 가장 낮은 학회원과 가장 높은 학회원을 서로 한 팀으로 묶는 것을 반복해도 팀 구성이 제대로 됨을 증명할 수 있다. (부등식을 잘 세워보자.)

따라서, 가장 능력치가 높은 사람부터 가능한 가장 낮은 능력치를 가진(그래도 능력치의 합이 \(M\) 이상은 되는) 학회원과 함께 팀으로 묶는 것을 반복하는 것으로 가장 많은 팀을 구성하는 하나의 경우를 얻을 수 있다.

이를 이용해 문제를 해결하자.

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

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

int N, M, L, R, ans;
int A[100000];

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

	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N);

	L = 0, R = N - 1;
	while (L < R) {
		if (A[L] + A[R] >= M) L++, R--, ans++;
		else L++;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 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;
}