취미로 코딩하기

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

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

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

먼저, 첫 친구가 오는 시점에 맞춰 난로를 키고 마지막 친구가 가는 시점에 맞춰 난로를 꺼야 함은 자명하다. 이 두 행동을 제외하고 생각하면 난로는 총 \(K-1\)번 끄고 킬 수 있다. 언제 이와 같은 조작을 하는 것이 난로가 켜진 시간을 최소화하는 전략일까?

문제를 (난로를 처음 키고 마지막으로 끈 시간 사이의) 난로가 꺼져있는 시간을 최대화하는 문제로 바꿔 생각해보자. 난로를 한번 끄고 킬 때 추가적으로 얻을 수 있는 "난로가 꺼져있는 시간"은 (인접한 시간에 오는 두 친구의 \(T_i\)값의 차 - 1)이 된다. 따라서 두 친구가 오는 시간간격들 중 그 차 가운데 가장 큰 \(K-1\)개를 골라 전체 구간(처음 난로를 켜야하는 때부터 마지막에 난로를 꺼야하는 때까지)에서 빼는 것으로 구할 수 있다. 이를 이용하면 난로가 켜져있는 시간을 최소화하는 문제 또한 같이 해결할 수 있게 된다.

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

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

int N, K;
priority_queue<int> pq;
int A[100000];
int ans;

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

	cin >> N >> K; K--;
	for (int i = 0; i < N; i++) cin >> A[i];
	ans = A[N - 1] - A[0] + 1;
	for (int i = 1; i < N; i++) pq.push(A[i] - A[i - 1] - 1);
	
	while (K--) {
		ans -= pq.top();
		pq.pop();
	}

	cout << ans;
}

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

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

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

먼저, 주어지는 소수들을 임의로 배치했을 때 각 행의 소수들의 곱의 값은 서로 다름을 관찰하자. 주어지는 소수들이 모두 다르므로 소인수분해의 결과가 서로 다를 수밖에 없기 때문이다.

따라서 주어진 소수들로 \(R\)개의 행을 구성했을 때, 이 행들을 주어진 가중치 순서대로 나열하는 방법은 유일하게 정해짐을 관찰할 수 있다.

따라서 이 문제는 주어진 소수들로 \(R\)개의 행을 구성하는 경우의 수(를 998244353으로 나눈 나머지)를 구하는 것으로 해결할 수 있다.

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

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

ll inv(ll X) {
	ll ret = 1, K = 998244351;
	while (K) {
		if (K & 1) ret = ret * X % 998244353;
		K >>= 1;
		X = X * X % 998244353;
	}
	return ret;
}

ll R, C, RR = 1, RC;
ll ans = 1;

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

	cin >> R >> C;
	RC = R * C;
	for (ll i = 1; i <= RC; i++) ans = (ans * i) % 998244353;
	for (ll i = 1; i <= R; i++) RR = (RR * i) % 998244353;
	RR = inv(RR);
	ans = ans * RR % 998244353;

	cout << ans;
}

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

이번에 볼 문제는 백준 18231번 문제인 파괴된 도시이다.
문제는 아래 링크를 확인하자.

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

어떤 도시에 폭탄이 떨어졌다면 해당 도시와 그 인접한 도시가 모두 파괴되므로, 어떤 도시가 파괴되지 않았거나 인접한 도시 중 파괴되지 않은 도시가 있다면 그 도시에는 폭탄이 떨어질 수 없음을 관찰하자. 또한 그 외의 도시에는 폭탄이 떨어질 수 있음을 관찰하자.

위에서 관찰한 "폭탄이 떨어질 수 있는 도시" 모두에 폭탄을 떨어트려도 파괴되지 않아야 하는 도시가 파괴되는 일은 발생하지 않는다. 따라서 해당 도시들에 폭탄을 모두 떨어트리는 시뮬레이션을 돌려 처음 주어진 형태대로 도시가 파괴되는지 확인해 문제를 해결할 수 있다.

도시는 많아야 2000개이므로 위와 같이 폭탄을 떨어트릴 수 있는 도시를 찾아 시뮬레이션하는 과정은 제한시간 내에 충분히 진행할 수 있다.

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

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

int N, M, K;
bool destroyed[2001];
bool chk[2001];
vector<int> G[2001];
vector<int> ans;

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

	cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	cin >> K;
	while (K--) {
		int x; cin >> x;
		destroyed[x] = 1;
	}
	for (int i = 1; i <= N; i++) {
		if (!destroyed[i]) continue;
		bool tmp = 1;
		for (auto &x : G[i]) {
			if (!destroyed[x]) tmp = 0;
		}
		if (tmp) {
			chk[i] = 1;
			for (auto &x : G[i]) chk[x] = 1;
			ans.emplace_back(i);
		}
	}

	for (int i = 1; i <= N; i++) {
		if (destroyed[i] && !chk[i]) {
			cout << -1;
			return 0;
		}
	}
	cout << ans.size() << '\n';
	for (auto &x : ans) cout << x << ' ';
}

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

이번에 볼 문제는 백준 12742번 문제인 혼합물 (Small)이다.
문제는 아래 링크를 확인하자.

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

12743번 문제와 같이 답이 유일함을 가정하겠다. 그리고 편의상 \(GA_i\)는 \(A_i\)로, \(GB_i\)는 \(B_i\)로 표기하겠다.

앞으로 만들 A의 양을 \(x\), B의 양을 \(y\)라 하자. 이 때 \(xA_i + yB_i\le W_i\)가 성립하며, 추가적으로 \(x\ge 0\), \(y\ge 0\)이 성립한다. 이때 주어진 문제는 \(xX+yY\)의 최댓값을 구하는 것으로 해결할 수 있다. 이는 LP(Linear Programming; 선형계획법) 문제로 볼 수 있다. 이 LP 문제를 해결해 문제를 풀어내자.

모든 조건을 만족하는 \(x\)와 \(y\)를 좌표평면 위에 나타내면 볼록다각형의 형태를 띄는데, LP의 해는 이 다각형의 경계에서 항상 찾을 수 있음이 잘 알려져있다. 특히 답이 유일한 경우 LP의 해는 이 다각형의 꼭짓점에서 항상 찾을 수 있다. 문제 조건(입력으로 주어지는 모든 수는 양의 정수)에 따라 해당 다각형은 항상 넓이가 양수임을 관찰하자.

이 다각형의 꼭짓점들은 직선들 \(xA_i + yB_i = W_i\) 및 \(x=0\), \(y=0\)의 교점에서 찾을 수 있으므로, 각 교점에 대하여 해당 교점이 다각형의 꼭짓점인지 판정하고 그 중 xX+yY의 최댓값을 구해 문제를 해결하자. 이 과정에서 두 직선이 평행해 교점이 없을 수도 있음에 유의해 구현하자. 또한 \(x\)축과 \(y\)축을 고려해야 함을 놓치지 말자. 아래의 글쓴이의 풀이는 직선의 쌍 \(O(N^2)\)가지에 대하여 두 직선의 교점이 다각형의 꼭짓점인지 각각 \(O(N)\)에 판정해 총 \(O(N^3)\)의 시간복잡도를 가진다. 이는 문제를 해결하기에 충분한 시간복잡도이다.

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

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

ll N, X, Y;
ll A[200], B[200], W[200];
ld ans1, ans2, ans;

void solve11(int i) {
	ld XX = (ld)W[i] / A[i];
	ld YY = 0;
	
	for (int k = 0; k < N; k++) {
		if (XX * A[k] + YY * B[k] > W[k]) return;
	}
	
	ld val = XX * X + YY * Y;
	if (val > ans) ans = val, ans1 = XX, ans2 = YY;
}
void solve12(int i) {
	ld XX = 0;
	ld YY = (ld)W[i] / B[i];
	
	for (int k = 0; k < N; k++) {
		if (XX * A[k] + YY * B[k] > W[k]) return;
	}
	
	ld val = XX * X + YY * Y;
	if (val > ans) ans = val, ans1 = XX, ans2 = YY;
}

void solve2(int i, int j) {
	if (A[i] * B[j] == A[j] * B[i]) return;
	ld XX = (ld)(W[i] * B[j] - W[j] * B[i]) / (A[i] * B[j] - A[j] * B[i]);
	ld YY = (ld)(W[j] * A[i] - W[i] * A[j]) / (A[i] * B[j] - A[j] * B[i]);
	
	if (XX < 0 || YY < 0) return;
	
	for (int k = 0; k < N; k++) {
		if (XX * A[k] + YY * B[k] > W[k]) return;
	}
	
	ld val = XX * X + YY * Y;
	if (val > ans) ans = val, ans1 = XX, ans2 = YY;
}

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

	cin >> N >> X >> Y;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> B[i];
	for (int i = 0; i < N; i++) cin >> W[i];

	for (int i = 0; i < N; i++) {
		solve11(i);
		solve12(i);
		for (int j = i + 1; j < N; j++) {
			solve2(i, j);
		}
	}

	cout << fixed;
	cout.precision(2);
	cout << ans << '\n' << ans1 << ' ' << ans2;
}

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

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

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

두 xor값이 같으려면 그 두 값을 다시 xor연산한 값은 0이 되어야 함을 관찰하자. 이는 즉 주어진 모든 수의 xor값이 0과 같아야 함을 의미한다.

위의 관찰을 토대로 조금 더 관찰하면 주어진 모든 수를 xor한 값이 0이 아니면 수를 어떻게 나누어도 xor이 0이 되게 할 수 없으므로 답은 0이 되고, 그렇지 않은 경우 어떻게 나누어도 항상 xor이 0이 되므로 답은 주어진 모든 수의 합에서 가장 작은 하나의 수를 뺀 값이 됨을 알 수 있다.

위 관찰을 이용해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;
int total, val, mn = 1000000007;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		total += x;
		val ^= x;
		mn = min(mn, x);
	}

	if (val) cout << 0;
	else cout << total - mn;
}

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

이번에 볼 문제는 백준 12843번 문제인 복수전공이다.
문제는 아래 링크를 확인하자.

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

"두 학부 간의", 즉 "두 학부 사이의" 겹치는 내용이 존재하는 강의 사이의 관계들이 입력으로 주어지므로, 같은 학부의 강의들 사이의 관계는 주어지지 않음을 관찰하자. 따라서 주어지는 과목들을 노드로, 관계를 에지로 하여 주어진 문제 상황을 그래프로 모델링하면 해당 그래프는 컴퓨터 학부 강의들의 집합과 소프트웨어 학부 강의들의 집합 사이에만 에지가 존재하는 이분그래프(bipartite graph)가 됨을 알 수 있다. 또한, 문제에서 구하고자하는 값은 해당 그래프에서 어떤 에지도 양 끝의 두 노드를 선택하지 않게끔 가장 많은 노드를 고를 때의 그 고른 노드 수와 같음을 알 수 있다. 즉, 이 문제는 이분그래프에서의 maximum independent set의 크기를 구하는 문제와 같음을 알 수 있다.

이분그래프에서의 maximum independent set의 크기는 전체 노드의 수에서 maximum bipartite matching의 수를 뺀 것과 같음은 잘 알려져있다. Kőnig's theorem(쾨니그의 정리)와 "maximum independet set과 minimum vertex cover 사이의 관계"를 이용하면 증명도 어렵지 않으므로 관련 내용을 잘 모른다면 이번에 알아보도록 하자.

위 내용을 이용해 문제를 해결하자.

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

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

int N, A, B, M;
vector<int> G[2001];
int idtoidx[2001];
int matching[2001];
int visited[2001];

int dfs(int cur) {
	visited[cur] = 1;
	for (auto &nxt:G[cur]) {
		if (!matching[nxt]) {
			matching[nxt] = cur;
			return 1;
		}
		else if (!visited[matching[nxt]] && dfs(matching[nxt])) {
			matching[nxt] = cur;
			return 1;
		}
	}
	return 0;
}

int ans;

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		int id; char c; cin >> id >> c;
		if (c == 'c') {
			A++;
			idtoidx[id] = A;
		}
		else {
			B++;
			idtoidx[id] = B + 2000;
		}
	}
	while (M--) {
		int x, y; cin >> x >> y;
		x = idtoidx[x], y = idtoidx[y];
		if (x > y) swap(x, y);
		G[x].emplace_back(y - 2000);
	}

	for (int i = 1; i <= A; i++) {
		memset(visited, 0, sizeof(visited));
		ans += dfs(i);
	}

	cout << N - ans;
}