취미로 코딩하기

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

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

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

칸을 이동해 만들어질 수 있는 각 상태를 노드로, 한 번의 조작으로 서로 바뀔 수 있는 관계를 양방향 에지로 하는 그래프를 모델링해보자. 이때, 주어진 상태에서 초기 상태를 만들기 위해 필요한 조작의 수는 위 그래프에서의 최단거리와 같음을 알 수 있다.

가능한 상태의 경우의 수는 9팩토리얼의 upper bound를 갖고(실제로는 이보다 더 적다), 각 상태에서 한 번의 조작으로 얻을 수 있는 다음 상태는 많아야 네 가지이므로 노드의 수와 에지의 수가 충분히 적음을 관찰하자. 따라서 위 그래프에서의 BFS 등을 이용해 문제를 해결할 수 있다.

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

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

vector<int> vecS(9);
vector<int> vecE(9);
map<vector<int>, int> mp;
map<vector<int>, int> btrk;
queue<vector<int>> que;

void bfs() {
	mp[vecS] = 0;
	que.push(vecS);
	while (!que.empty()) {
		auto cur = que.front(); que.pop();
		int d = mp[cur];
		int idx = 0; while (cur[idx] != 9) idx++;
		if (idx - 3 >= 0) {
			swap(cur[idx], cur[idx - 3]);
			if (!mp.count(cur)) {
				mp[cur] = d + 1;
				que.push(cur);
				btrk[cur] = cur[idx];
			}
			swap(cur[idx], cur[idx - 3]);
		}
		if (idx + 3 < 9) {
			swap(cur[idx], cur[idx + 3]);
			if (!mp.count(cur)) {
				mp[cur] = d + 1;
				que.push(cur);
				btrk[cur] = cur[idx];
			}
			swap(cur[idx], cur[idx + 3]);
		}
		if (idx % 3) {
			swap(cur[idx], cur[idx - 1]);
			if (!mp.count(cur)) {
				mp[cur] = d + 1;
				que.push(cur);
				btrk[cur] = cur[idx];
			}
			swap(cur[idx], cur[idx - 1]);
		}
		if (idx % 3 < 2) {
			swap(cur[idx], cur[idx + 1]);
			if (!mp.count(cur)) {
				mp[cur] = d + 1;
				que.push(cur);
				btrk[cur] = cur[idx];
			}
			swap(cur[idx], cur[idx + 1]);
		}
	}
}

vector<int> ans;

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

	for (int i = 0; i < 9; i++) {
		char c; cin >> c;
		if (c == 'X') c = '9';
		vecS[i] = c - '0';
	}
	for (int i = 0; i < 9; i++) vecE[i] = i + 1;
	bfs();

	cout << mp[vecE] << '\n';
	while (btrk.count(vecE)) {
		int x = btrk[vecE];
		ans.emplace_back(x);
		int idx = 0, jdx = 0;
		while (vecE[idx] != x) idx++;
		while (vecE[jdx] != 9) jdx++;
		swap(vecE[idx], vecE[jdx]);
	}

	while (!ans.empty()) {
		cout << ans.back() << '\n';
		ans.pop_back();
	}
}

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

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

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

각각의 칸을 노드로, 인접한 두 칸 A와 B에 대하여 A에서 B로 이동할 수 있는 관계를 에지로(가중치는 B의 복구비용) 갖는 그래프를 생각해보자. 이 때, 좌상단 칸에서 우하단 칸까지의 최단경로는 (좌상단 칸이 방문 가능하다는 가정 하에) 위에서 모델링한 그래프에서의 최단경로와 대응시켜 생각해볼 수 있다.

가능한 에지 가중치의 종류가 적고 가중치의 크기가 작으므로 큐를 이용한 dijkstra 또는 dial's algorithm 등도 사용할 수 있겠지만, 그냥 dijktra 알고리즘을 이용해도 무리없이 문제를 해결할 수 있다.

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

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

int R, C;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
int board[1000][1000];
int dist[1000][1000];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	dist[0][0] = board[0][0];
	pq.push(make_pair(board[0][0], 0));
	while (!pq.empty()) {
		int r = pq.top().second / C, c = pq.top().second % C, d = pq.top().first; pq.pop();
		if (dist[r][c] < d) continue;
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == -1) continue;
			int dd = d + board[rr][cc];
			if (dd < dist[rr][cc]) dist[rr][cc] = dd, pq.push(make_pair(dd, rr * C + cc));
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
		}
	}
	if (board[0][0] == -1 || board[R - 1][C - 1] == -1) {
		cout << -1;
		return 0;
	}

	dijkstra();

	if (dist[R - 1][C - 1] < 0x3f3f3f3f) cout << dist[R - 1][C - 1];
	else cout << -1;
}

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

이번에 볼 문제는 백준 13270번 문제인 피보나치 치킨이다.
문제는 아래 링크를 확인하자.

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

2인 1닭, 3인 2닭을 제외한 모든 n인 m닭 조합은 앞의 두 조합을 섞어 만들 수 있음을 관찰하자.

따라서 2인 1닭과 3인 2닭만을 이용한 조합만을 이용하는 경우만을 생각해 문제를 충분히 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N;

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

	cin >> N;
	if (N % 2) cout << 2 + (N - 3) / 2 << ' ';
	else cout << N / 2 << ' ';

	if (N % 3 == 1) cout << 2 + (N - 4) / 3 * 2;
	else if (N % 3 == 2) cout << 1 + (N - 2) / 3 * 2;
	else cout << N / 3 * 2;
}

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

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

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

연속한 두 스텝이 올바른 동작을 구성하려면 (1) 각 스텝의 두 번째 문자가 서로 일치해야하며 (2) 첫 번째 문자가 서로 달라야 함을 알 수 있다. 이를 이용해 처음서부터 두 개의 스텝씩 묶어 읽어나갈 때 "올바른 동작"이 몇 개 있는지를 세어 문제를 해결하자.

같은 동작은 여러 "올바른 동작"에 포함될 수 없음에 유의하자.

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

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

int N;
vector<string> vec;

void solve() {
	int ans = 0;
	vec.clear();
	for (int i = 0; i < N; i++) cin >> vec.emplace_back();
	for (int i = 1; i < N; i++) {
		if (vec[i].back() == vec[i - 1].back() && vec[i].front() != vec[i - 1].front()) ans++, i++;
	}
	cout << ans << '\n';
}

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

	cin >> N;
	while (N) {
		solve();
		cin >> N;
	}
}

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

이번에 볼 문제는 백준 17086번 문제인 아기 상어 2이다.
문제는 아래 링크를 확인하자.

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

주어진 모든 \(NM\)개의 칸에 대하여, 상어가 있는 \(O(NM)\)개의 칸과의 거리를 각각 확인해 안전거리를 계산하고, 그 중 가장 큰 값을 계산해 문제를 해결하자. 두 칸 사이의 안전거리는 (행의 차이)와 (열의 차이) 중 더 큰 값과 같다.

위와 같은 풀이의 시간복잡도는 \(O(N^2M^2)\)으로, \(N\)과 \(M\)이 최대 50이므로 이는 문제를 해결하기에 충분한 시간복잡도임을 알 수 있다.

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

#include <iostream>
using namespace std;

int R, C;
int A[50][50];
int ans;

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> A[r][c];
		}
	}
	for (int rr = 0; rr < R; rr++) {
		for (int cc = 0; cc < C; cc++) {
			int mn = 1000000007;
			for (int r = 0; r < R; r++) {
				for (int c = 0; c < C; c++) {
					if (A[r][c]) mn = min(mn, max(abs(r - rr), abs(c - cc)));
				}
			}
			ans = max(ans, mn);
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 18119번 문제인 단어 암기이다.
문제는 아래 링크를 확인하자.

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

알고 있는 문자의 집합이 바뀔 때마다 모든 단어를 구성하는 문자를 하나하나 확인하는 것은 매우 비효율적이다. 이를 어떻게 효율적으로 바꿀 수 있을까?

먼저, 어떤 단어를 알기 위해서는 그 단어를 구성하는 어떤 문자가 1회 사용되어도 다회 사용되어도 그 문자를 알고 있어야 한다는 사실을 관찰하자. 따라서 각 단어를 알고 있는지의 여부를 확인하기 위해 해당 문자를 구성하는 문자의 집합만을 관리해도 문제가 없음을 알 수 있다. 알파벳 소문자는 26가지뿐이므로, 각 집합의 원소는 많아야 26개가 될 것이다.

여기에서 더 나아가 해당 집합은 i번째 알파벳이 존재할 경우 i번째 비트가 1, 그렇지 않을 경우 i번째 비트가 0인 크기 26의 비트셋으로 나타낼 수 있음을 관찰하자.

이를 이용하면 각 단어를 알고 있는지를 확인하는 것은 bitwise and 연산을 이용해 매우 빠르게 진행할 수 있게 된다. 이 점을 이용해 문제를 해결하자.

\(NM\)의 상한은 5억이고 제한시간이 4초임을 확인하자. 또한 4초에 5억회의 비트연산은 충분히 실행할 수 있음을 상기하자. 실제로 글쓴이의 코드는 1초 미만으로 문제를 해결하였다.

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

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

int N, M;
int A[10000];
int mm = 67108863;

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

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int &x = A[i];
		string s; cin >> s;
		for (auto &l : s) x |= (1 << (l - 'a'));
	}

	while (M--) {
		int ans = 0;
		char c; cin >> c >> c;
		mm ^= (1 << (c - 'a'));
		for (int i = 0; i < N; i++) {
			if ((A[i] & mm) == A[i]) ans++;
		}
		cout << ans << '\n';
	}
}