취미로 코딩하기

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

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

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

주어진 문제에서 차의 상태는 주어진 격자의 좌표 \((x,y)\)와 차가 바라보고 있는 방향 \(d\)를 묶은 순서쌍 \(((x,y),d)\)들로 표현할 수 있다. 이러한 각 상태를 노드로, 한 상태에서 다른 상태로의 변화를 그 때 들어가는 비용을 가중치로 갖는 에지로 생각하면 주어진 문제상황은 가중치 있는 방향그래프에서 최단거리를 구하는 문제로 모델링할 수 있게 된다.

이는 대표적으로 dijkstra 알고리즘을 이용하여 해결할 수 있다.

유턴을 할 수 있는 조건의 구현에 특히 유의하자.

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

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

int R, C, sR, sC, sdir, eR, eC;
string board[30];
int dist[30][30][4];

priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
int dr[4] = {1,0,-1,0};
int dc[4] = {0,-1,0,1};
int cost[4] = {0,5,10,1};

void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	dist[sR][sC][sdir] = 0;
	pq.push(make_pair(0, make_pair(sR * 1000 + sC, sdir)));
	while (!pq.empty()) {
		int r = pq.top().second.first / 1000, c = pq.top().second.first % 1000, dir = pq.top().second.second, w = pq.top().first; pq.pop();
		if (dist[r][c][dir] < w) continue;
		int mvtry = 0;
		for (int i = 0; i < 4; i++) {
			if (i == 2) continue;
			int ddir = (dir + i) % 4;
			int rr = r + dr[ddir], cc = c + dc[ddir];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (board[rr][cc] != '#') continue;
			mvtry++;
			int ww = dist[r][c][dir] + cost[i];
			if (ww < dist[rr][cc][ddir]) dist[rr][cc][ddir] = ww, pq.push(make_pair(ww, make_pair(rr * 1000 + cc, ddir)));
		}
		if (!mvtry) {
			int i = 2;
			int ddir = (dir + i) % 4;
			int rr = r + dr[ddir], cc = c + dc[ddir];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (board[rr][cc] != '#') continue;
			mvtry++;
			int ww = dist[r][c][dir] + cost[i];
			if (ww < dist[rr][cc][ddir]) dist[rr][cc][ddir] = ww, pq.push(make_pair(ww, make_pair(rr * 1000 + cc, ddir)));
		}
	}
}

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		cin >> board[r];
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == 'F') {
				eR = r, eC = c;
				board[r][c] = '#';
			}
			else if (board[r][c] == 'S') {
				sR = r, sC = c, sdir = 0;
				board[r][c] = '#';
			}
			else if (board[r][c] == 'W') {
				sR = r, sC = c, sdir = 1;
				board[r][c] = '#';
			}
			else if (board[r][c] == 'N') {
				sR = r, sC = c, sdir = 2;
				board[r][c] = '#';
			}
			else if (board[r][c] == 'E') {
				sR = r, sC = c, sdir = 3;
				board[r][c] = '#';
			}
		}
	}

	dijkstra();

	cout << min(min(dist[eR][eC][0], dist[eR][eC][1]), min(dist[eR][eC][2], dist[eR][eC][3]));
}

BOJ Random Defense #11

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

이번에 볼 문제는 백준 1727번 문제인 커플 만들기이다.
문제는 아래 링크를 확인하자.

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

남자와 여자를 이어줄 때 둘의 성격의 차이를 "비용"이라 부르겠다.

먼저 남자들과 여자들의 성격수치를 각각 오름차순으로 정렬하자. 이때, \(k\)명의 남자와 \(k\)명의 여자를 고른 경우 이들을 모두 이어주면서 그 비용을 최소화하는 방법은 성격수치 순서대로 이어주는 것임을 관찰하자. (증명은 exchange argument로 할 수 있다.)

위 관찰을 이용하면, \(p\ge q\)이라 할 때 \(p\)번째 남자까지 봤을 때 \(q\)번째 여자까지 비용을 최소로 매칭시킬 때의 비용은 (1) \(q\)번째 여자를 \(p\)번째 남자에게 매칭시키거나, (2) 그렇지 않은 두 가지 경우가 있다는 점을 이용해 점화식을 세울 수 있게 된다. 여기서 (1)의 값을 구하고자 할 때 \(q-1\)번째 여자를 \(p-1\)이하번째 남자에게 매칭시킬 때의 최소 비용을 알아야 하는데, 이 또한 메모이제이션을 통해 반복계산을 줄여 충분히 빠르게 구할 수 있음을 관찰하자.

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

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

int N, M;
int mn[1001][1001], dp[1001][1001]; bool mvisited[1001][1001], visited[1001][1001];// [N][M]이 마지막 매칭인 최솟값
int A[1001], B[1001];

int func(int n, int m);

int mnfunc(int n, int m) {
	if (n < m) return 0x3f3f3f3f;
	if (!m) return 0;
	int &ret = mn[n][m];
	if (mvisited[n][m]) return ret;
	mvisited[n][m] = 1;
	ret = func(n, m);
	ret = min(ret, mnfunc(n - 1, m));
	return ret;
}

int func(int n, int m) {
	int &ret = dp[n][m];
	if (visited[n][m]) return dp[n][m];
	visited[n][m] = 1;
	ret = mnfunc(n - 1, m - 1) + abs(A[n] - B[m]);
	return ret;
}

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

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

	if (N < M) swap(N, M), swap(A, B);
	cout << mnfunc(N, M);
}

처음 이 문제를 접근할 때의 글쓴이가 했던 생각을 같이 남겨둔다.

글쓴이는 처음에 이 문제를 성격수치가 \(x\)인 남자와 \(y\)인 여자를 짝지어줄 때의 비용을 \(x-y\)의 절댓값으로 나타낼 때, minimum weight maximal bipartite matching의 그 가중치 총합을 구하는 문제로 보았다. 이 점에 초점을 맞춰 MCMF로 문제를 해결하려고 시도했으나, 시간초과로 해결하지 못했다. 다만, 이후에 몇몇 성질을 이용해 불필요한 간선 일부를 줄인 그래프 모델링과 MCMF로 뚫는 데에 성공하기는 했다.

헝가리안 알고리즘(Hungarian algorithm; Kuhn-Munkres Algorithm)은 구현해본 적이 없어 확인하지 않았는데 (안될 것 같지만) 이걸로도 풀릴까...?

BOJ Random Defense #10 (실패: 제한시간초과)

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

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

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

먼저, 마지막 원소를 제외한 각 원소에 대하여 적어도 길이 1의 배열에 대한 Reverse 연산을 진행해야함을 확인하자. 따라서 총 \(N-1\)단계를 진행한다는 점을 이용하면 \(C\)의 값이 \(N-1\) 이상이어야 함을 알 수 있다.

또한 마지막 원소를 제외한 각 원소에 대하여 가장 오른쪽 원소까지 뒤집는 연산을 해야 하는 경우가 비용이 가장 큰 경우가 될 것이다. 따라서 \(C\) 값이 \(N(N+1)/2-1\) 이하여야 함을 알 수 있다.

reversort의 과정을 역으로 뒤집어 생각해보자. 각 단계에서, 길이 \(k\)의 부분배열을 뒤집어 정렬된 위치로 이동하게 되는 "가장 작은 원소"의 이동거리를 원하는 대로 설정할 수 있음을 관찰하면, 이를 이용해 (불가능한 경우가 아닌) 임의의 \(C\)에 대하여 문제의 답이 되는 배열을 구성하는 알고리즘을 설계하는 것은 어렵지 않을 것이다.

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

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

int N, C;
vector<int> vec;
vector<int> ans;

void solve() {
	vec.clear(), ans.clear();
	cin >> N >> C; 
	if (C < N - 1) {
		cout << "IMPOSSIBLE\n";
		return;
	}
	
	C -= N - 1;
	for (int i = 1; i < N; i++) {
		int val = min(C, i);
		vec.emplace_back(val + 1);
		C -= val;
	}
	
	if (C) {
		cout << "IMPOSSIBLE\n";
		return;
	}

	for (int i = 1; i <= N; i++) ans.emplace_back(i);
	for (int i = 0, L = N - 2; i + 1 < N; i++, L--) {
		int LL = L, RR = L + vec[i] - 1;
		while (LL < RR) {
			swap(ans[LL], ans[RR]);
			LL++, RR--;
		}
	}
	for (auto &x : ans) cout << x << ' ';
	cout << '\n';
}

int T;

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

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

BOJ Random Defense #9

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

이번에 볼 문제는 백준 9176번 문제인 메르센 합성수이다.
문제는 아래 링크를 확인하자.

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

주어진 범위의 메르센 수 중 합성수를 소인수분해한 결과를 출력하는 문제이다.

주어진 범위에서 소인수분해를 해야 하는 가장 큰 수는 "2,305,843,009,213,693,951"인데, 이 정도의 큰 수를 빠르게 소인수분해하는 것은 어려운 문제이다. (CP 환경에서 주로 주어지는 범위의 수에는 일반적으로 Pollard's Rho 등의 알고리즘을 사용한다.) 그러나 이 문제의 경우 확인할 필요가 있는 큰 수는 몇 가지 없으므로, 가능한 모든 메르센 수를 직접 소인수분해한 결과를 하드코딩하는 방법으로도 문제를 충분히 해결할 수 있다.

아래는 소인수분해 과정에 사용한 간단한 코드이다. 해당 코드의 방식을 이용한 구현을 그대로 제출할 경우 제한시간 내로 문제를 해결할 수 있다고 확신할 수는 없지만, 필요한 값 자체를 미리 얻어 하드코딩하기에는 충분히 빠름을 확인하자.

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

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

ll N;

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

	cin >> N;
	N = (1LL << N) - 1;

	for (ll i = 3; i * i <= N; i += 2) {
		while (!(N % i)) {
			N /= i;
			cout << i << ' ';
		}
	}
	cout << "\nDONE!";
}

(BOJ Random Defense #8)

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

이번에 볼 문제는 백준 7146번 문제인 데이터 만들기 7이다.
문제는 아래 링크를 확인하자.

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

백트래킹이 빠른 알고리즘은 아니기에 적절한 그래프를 대충 구성해주기만 해도 주어진 문제의 코드의 연산량을 크게 할 수 있다.

다만 여기서 주의해야 할 점은 연산량이 매우 많다는 것과 "counter 변수의 값이 1000000을 넘겼다"는 것이 동치가 아니라는 점이다. counter 변수는 부호있는 32비트 정수 자료형인 int로 선언되어있어 연산량이 매우 커질 경우 오버플로우가 일어나게 된다. 따라서 그냥 단순히 오래 걸리는 데이터를 만들 경우 약 절반의 확률로 counter 변수의 값이 음수가 되어 틀릴 수도 있다.

적당한 그래프를 구성해 주어진 코드의 counter 변수가 실제로 1000000이 넘는 값으로 실행을 마치는지 직접 확인한 다음 답으로 제출하자.

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

#include <iostream>
using namespace std;

int V = 999, E = 1501;
int a = 60, b = 61;

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

	cout << V << ' ' << E << '\n';
	for (int e = 0; e < E; e++) {
		if (b > 61) {
			b = a;
			a--;
		}
		cout << a << ' ' << b << '\n';
		b++;
	}
}

(BOJ Random Defense #6)

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

이번에 볼 문제는 백준 24229번 문제인 모두싸인 출근길이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/probelm/24229

필요한 관찰을 먼저 해보자.

(1) 어떤 두 판자가 같은 점을 공유한다면, 해당 두 판자는 하나의 긴 판자로 생각해도 무방함을 관찰하자.

(2) 위의 관찰에 따라 같은 점을 공유하는 판자들을 하나의 큰 판자로 바꿔 생각하면, 주어진 문제는 판자들이 서로 겹치지 않게 모델링이 가능하다.

(3) 어떤 판자에서 (판자로 연결되지 않은) 다른 판자로 점프해 이동할 수 있다면, 해당 판자의 가장 왼쪽 끝점으로 점프하는 것이 항상 이득이다. 다음 점프로 도달할 수 있는 거리를 최대화할 수 있기 때문이다.

이 두 관찰에 따라, 출발점(0)부터 시작해 점프를 통해 도착할 수 있는 좌표의 범위와 도달할 수 있는 거리(도착할 수 있는 최대 좌표)의 값을 관리하면서 판자들을 차례대로 살펴 문제를 해결하자.

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

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

int N;
vector<pair<int, int>> vec, seg;
int tmpL, tmpR;
int ans, reachable;

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

	cin >> N;
	while (N--) {
		int L, R; cin >> L >> R;
		vec.emplace_back(L, R);
	}
	sort(vec.begin(), vec.end());
	for (auto &p : vec) {
		if (tmpR < p.first) {
			seg.emplace_back(make_pair(tmpL, tmpR));
			tmpL = p.first, tmpR = p.second;
		}
		else tmpR = max(tmpR, p.second);
	}
	seg.emplace_back(make_pair(tmpL, tmpR));

	for (auto &p : seg) {
		if (reachable < p.first) break;
		ans = max(ans, p.second);
		reachable = max(reachable, p.first + (p.second - p.first) * 2);
	}

	cout << ans;
}

(BOJ Random Defense #1)