취미로 코딩하기

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

이번에 볼 문제는 백준 13021번 문제인 공 색칠하기이다.
문제는 아래 링크를 확인하자.

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

어떤 색칠의 결과가 최종 결과에 영향을 준다면 해당 색칠을 어떤 색으로 하였는지에 따라 구하는 경우의 수의 값이 2배가 됨을 관찰하자.

색칠을 역순으로 살펴나가면서 이후로 위에 색이 덧칠되지 않을 칸이 해당 색칠에 존재하는지를 살피면 각 색칠의 결과가 최종 결과에 영향을 주는지를 알 수 있다.

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

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

int N, M;
ll ans = 1;
bool visited[1001];
vector<pair<int, int>> vec;

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

	cin >> N >> M;
	while (M--) {
		int L, R; cin >> L >> R;
		vec.emplace_back(make_pair(L, R));
	}
	while (!vec.empty()) {
		int L = vec.back().first, R = vec.back().second; vec.pop_back();
		bool chk = 0;
		for (int i = L; i <= R; i++) {
			if (visited[i]) continue;
			visited[i] = 1, chk = 1;
		}
		if (chk) ans *= 2;
	}
	cout << ans;
}

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

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

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

범위 내의 서로 다른 정수로 구성된, 순서대로 등차수열을 이루는 모든 세 수의 쌍에 대하여 해당 쌍들이 주어진 순서대로 주어지는지 하나하나 확인해 문제를 해결하자.

이는 각 수가 수열의 몇 번째 항으로 등장하는지 저장하는 배열을 준비하는 것으로 빠르게 해낼 수 있다.

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

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

int N;
int A[10001];
void solve() {
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		A[x] = i;
	}
	for (int i = 0; i < N; i++) {
		for (int g = 1; i - g > -1 && i + g < N; g++) {
			int sgn = 0;
			if (A[i - g] < A[i]) sgn ^= 1;
			if (A[i + g] < A[i]) sgn ^= 1;
			if (sgn) {
				cout << "no\n";
				return;
			}
		}
	}
	cout << "yes\n";
}

string s;

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

	cin >> s;
	while (s.back() == ':') {
		s.pop_back();
		N = stoi(s);
		solve();
		cin >> s;
	}
}

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

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