취미로 코딩하기

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

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

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

벨 나무들을 먼저 결정한다면, 남은 나무를 감싸는 울타리의 최소 길이는 남은 나무들로 이루어진 Convex Hull의 둘레의 길이와 같음을 관찰하자.

이 둘레의 길이가 베어진 나무로 만들 수 있는 울타리의 길이보다 작거나 같은 모든 경우를 찾아 각 경우의 베어진 나무의 가치의 합을 계산하고, 그 중 최솟값을 찾아 문제를 해결하자. 전체 나무 수\(N\)의 값이 16 이하로 매우 작으므로 모든 경우를 조사해도 충분히 문제를 해결할 수 있다.

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long double ld;

struct point {
	int x, y, v, l;
	point() {};
	bool operator< (point &p) {
		if (x != p.x) return x < p.x;
		return y < p.y;
	}
};

int CCW(point &p1, point &p2, point &p3) {
	return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p1.x * p3.y - p2.x * p1.y - p3.x * p2.y;
}

int N, NN;
point P[16];
int ans = 1000000007;
vector<point> uhull, lhull;

void buildhull(int cN) {
	uhull.clear();
	for (int i = 0, b = 1; i < N; i++, b <<= 1) {
		if (cN & b) continue;
		while (uhull.size() > 1) {
			if (CCW(uhull[uhull.size() - 2], uhull.back(), P[i]) < 0) break;
			uhull.pop_back();
		}
		uhull.emplace_back(P[i]);
	}
	lhull.clear();
	for (int i = 0, b = 1; i < N; i++, b <<= 1) {
		if (cN & b) continue;
		while (lhull.size() > 1) {
			if (CCW(lhull[lhull.size() - 2], lhull.back(), P[i]) > 0) break;
			lhull.pop_back();
		}
		lhull.emplace_back(P[i]);
	}

	ld d = 0; int v = 0, l = 0, usize = uhull.size(), lsize = lhull.size();
	for (int i = 0; i + 1 < usize; i++) {
		d += hypotl(abs(uhull[i + 1].x - uhull[i].x), abs(uhull[i + 1].y - uhull[i].y));
	}
	for (int i = 0; i + 1 < lsize; i++) {
		d += hypotl(abs(lhull[i + 1].x - lhull[i].x), abs(lhull[i + 1].y - lhull[i].y));
	}
	for (int i = 0, b = 1; i < N; i++, b <<= 1) {
		if (!(cN & b)) continue;
		v += P[i].v, l += P[i].l;
	}
	if (d > l) return;
	ans = min(ans, v);
}

void solve() {
	NN = 1 << N;
	for (int i = 0; i < N; i++) cin >> P[i].x >> P[i].y >> P[i].v >> P[i].l;
	sort(P, P + N);
	ans = 1000000007;
	for (int i = 0; i + 1 < NN; i++) buildhull(i);
	cout << "The lost value is " << ans << ".\n";
}

int T;

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

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

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

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

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

지문에 Transitive Closure이라는 cp에서 자주 보이지는 않는 용어가 등장하지만 문제의 설명만으로도 충분히 구해야하는 것을 알 수 있다. 주어진 방향그래프 위에서 점 \(r\)로부터 점 \(c\)로 가는 경로가 존재하면 \(r\)행 \(c\)열 성분이 1, 아니면 0인 \(V\)행 \(V\)열의 1의 개수, 즉 각 점으로부터 도달가능한 (자기 자신이 아닌) 점의 개수의 합을 구하자.

모든 점에서 다른 점으로의 도달 가능성을 확인하는 것은 지문에서 언급된 방법인 (Floyd-)Warshall 알고리즘을 사용하는 것으로도 가능하지만 이 문제에서 사용하기에는 시간복잡도가 크다. 그러면 이 문제를 어떻게 해결해야 할까?

이 문제에서는 이동 거리에는 신경쓸 필요 없이 이동 가능성만을 고려하면 된다는 점에 주목하자. 이 점에 주목하면 Floyd-Warshall 알고리즘까지 사용할 필요 없이 각 점을 시작점으로 하는 그래프 탐색 알고리즘(DFS, BFS)을 사용해 문제를 해결할 수 있음을 관찰할 수 있다.

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

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

int V, E;
vector<int> G[2501];
int visited[2501];
queue<int> que;
int ans;

void solve() {
	ans = 0;
	cin >> V >> E;
	for (int v = 1; v <= V; v++) G[v].clear();
	while (E--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
	}

	for (int i = 1; i <= V; i++) {
		memset(visited, 0, sizeof(visited));
		visited[i] = 1;
		que.push(i);
		int cnt = -1;
		while (!que.empty()) {
			int cur = que.front(); que.pop();
			cnt++;
			for (auto &nxt:G[cur]) {
				if (visited[nxt]) continue;
				visited[nxt] = 1;
				que.push(nxt);
			}
		}
		ans += cnt;
	}
	cout << ans << '\n';
}

int T;

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

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

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

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

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

문제에서 요구하는 성질을 만족하는 수열은 여러 가지 있지만, 가장 잘 알려진 수열은 아마 그레이 코드(Gray Code)일 것이다. 정수를 이러한 이진수에 대응시키면 1을 더하거나 빼는 작업을 정확히 하나의 비트만을 조작하는 것으로 할 수 있게 된다.

그레이 코드의 \(n\)번째 수는 \(n\)과 \(n>>1\)의 xor로 계산할 수 있다. 여기서 \(>>\)는 logical right shift 연산을 뜻한다. 이를 이용해 각 수를 이진법으로 출력하고 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;

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

	cin >> N; N = 1 << N;
	for (int i = 0; i < N; i++) {
		int val = i ^ (i >> 1);
		for (int b = N / 2; b; b >>= 1) {
			if (val & b) cout << 1;
			else cout << 0;
		}
		cout << '\n';
	}
}

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

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

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

난민이 어떤 \(x\)좌표에 살더라도 일단 \(x\)축 방향으로 강이 있는 위치인 0으로는 이동해야 함을 관찰하자. \(x\)축 방향 움직임과 \(y\)축 방향 움직임은 독립적이므로 난민이 추가될 때마다 난민들의 \(x\)축 방향으로의 움직인 거리의 총합을 관리해주면 남는 것은 \(y\)축 방향으로의 난민들의 움직이는 거리를 최적화하는 것이다.

\(y'\)을 지금까지 추가된 난민들의 \(y\)좌표의 중앙값(median)이라 하자. 이 때 \(y'\) 이하의 \(y\)좌표 중 난민이 있는 좌표의 아래, 혹은 \(y'\) 이상의 \(y\)좌표 중 난민이 있는 좌표의 위에 정수시설을 설치하면 \(y'\)에 설치할 때보다 이동 거리 총합이 항상 늘어남을 어렵지 않게 관찰할 수 있다. 이로부터 매 순간 정수시설을 설치해야 하는 위치를 결정지을 수 있게 된다. 이 위치를 찾는 것은 running median 문제를 푸는 것과 같다.

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

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

int N, X;
priority_queue<int> L;
priority_queue<int, vector<int>, greater<>> R;
ll lsum, rsum, xtotal;

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

	L.push(-1000000007), R.push(1000000007);

	cin >> N;
	while (N--) {
		cin >> X;
		xtotal += abs(X);
		cin >> X;
		if (X < R.top()) {
			L.push(X);
			lsum += X;
			if (L.size() == R.size() + 2) {
				lsum -= L.top();
				rsum += L.top();
				R.push(L.top());
				L.pop();
			}
		}
		else {
			R.push(X);
			rsum += X;
			if (R.size() == L.size() + 2) {
				rsum -= R.top();
				lsum += R.top();
				L.push(R.top());
				R.pop(); 
			}
		}

		if (L.size() == R.size()) cout << L.top() << ' ' << xtotal + (ll)L.top() * (L.size() - 1) - lsum + rsum - (ll)L.top() * (R.size() - 1);
		else if (L.size() > R.size()) cout << L.top() << ' ' << xtotal + (ll)L.top() * (L.size() - 1) - lsum + rsum - (ll)L.top() * (R.size() - 1);
		else cout << R.top() << ' ' << xtotal + (ll)R.top() * (L.size() - 1) - lsum + rsum - (ll)R.top() * (R.size() - 1);
		cout << '\n';
	}
}

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

이번에 볼 문제는 백준 17262번 문제인 팬덤이 넘쳐흘러이다.
문제는 아래 링크를 확인하자.

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

모든 구간이 다 겹치는 시간이 있는 경우 답이 0이 됨은 자명하다. 그러한 구간이 없는 경우를 생각해보자.

욱제는 "가장 빨리 학교를 떠나는 학생"에게 인사를 해야 하므로 주어지는 R의 값의 최솟값인 시각에는 학교에 있어야 함을 알 수 있다. 마찬가지로 욱제는 "가장 늦게 학교에 오는 학생"에게 인사를 해야 하므로 주어지는 L의 값의 최댓값인 시각에도 학교에 있어야 함을 알 수 있다. 따라서 욱제는 학교에 못해도 "R의 최솟값" 시각부터 "L의 최댓값" 시각까지는 학교에 있어야 한다.

한편, 위와 같은 시간동안 학교에 머무르면 모든 학생들과 인사를 할 수 있음을 쉽게 관찰할 수 있다. 이를 이용해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;
int L = -1000000007, R = 1000000007;

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

	cin >> N;
	while (N--) {
		int x, y; cin >> x >> y;
		L = max(L, x);
		R = min(R, y);
	}

	cout << max(0, L - R);
}

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

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

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

주어진 좌표의 범위가 작다는 점을 이용해 범위 내의 각 정수 \(x\)에 대하여 \((x,y)\)가 삼각형 내부에 있는 격자점이 되는 범위 내의 정수 \(y\)의 개수를 계산해 합하는, \(x\)좌표의 범위에 비례한 선형 풀이로도 문제를 해결할 수 있을 것으로 예상되지만, 이 글에서는 다른 풀이인 픽의 정리(Pick's Theorem)을 이용한 풀이를 알아보자.

픽의 정리는 격자점만을 꼭짓점으로 갖는 단순다각형(simple polygon)의 넓이 \(A\)와 다각형의 경계에 있는 격자점의 개수 \(b\), 그리고 내부에 있는 격자점의 개수 \(i\)에 대하여 \(A=i+\frac{b}{2}-1\)과 같은 관계식이 성립한다는 내용을 담고 있다. 삼각형의 넓이는 사선공식(shoelace formula)을 이용해 어렵지 않게 구할 수 있고 다각형의 경계에 있는 격자점의 개수는 각 변(선분) 위의 격자점의 개수를 구하는 것으로 간단히 구할 수 있다는 점을 관찰하면, 다각형 내부의 격자점의 개수는 픽의 정리를 통해 어렵지 않게 구할 수 있음을 관찰할 수 있다.

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

#include <iostream>
using namespace std;

int gcd(int x, int y) {
	if (y) return gcd(y, x % y);
	return x;
}

int X1, Y1, X2, Y2, X3, Y3;
int A;

void solve() {
	A = abs(X1 * Y2 + X2 * Y3 + X3 * Y1 - X1 * Y3 - X2 * Y1 - X3 * Y2);
	int b = 0;
	{
		int dx = abs(X2 - X1), dy = abs(Y2 - Y1);
		b += gcd(dx, dy);
	}
	{
		int dx = abs(X3 - X2), dy = abs(Y3 - Y2);
		b += gcd(dx, dy);
	}
	{
		int dx = abs(X1 - X3), dy = abs(Y1 - Y3);
		b += gcd(dx, dy);
	}

	cout << (A - b + 2) / 2 << '\n';
}

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

	cin >> X1 >> Y1 >> X2 >> Y2 >> X3 >> Y3;
	while (X1 || Y1 || X2 || Y2 || X3 || Y3) {
		solve();
		cin >> X1 >> Y1 >> X2 >> Y2 >> X3 >> Y3;
	}
}