취미로 코딩하기

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

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

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

A > B와 같은 관계를 A에서 B로 가는 에지로 하는 방향그래프를 만들었을 때, 사이클이 존재한다면 inconsistent한 입력이고, 그렇지 않다면 consistent한 입력이 될 것이다.

단, C = D와 같은 관계가 있다면 C와 D를 같은 점으로 취급할 수 있으므로, 이것을 disjoint set을 이용하여 관리해주자.

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

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

int uf[50001];
int findf(int x) {
	if (x == uf[x]) return x;
	return uf[x] = findf(uf[x]);
}

vector<pair<int, int>> queries;

vector<int> G[50001];
bool visited[50001];
bool done[50001];

bool chk = 0;

void dfs(int current) {
	visited[current] = 1;
	int oldnode = 0;
	for (auto node : G[current]) {
		if (node == oldnode) continue;
		oldnode = node;
		if (visited[node]) {
			if (!done[node]) chk = 1;
			continue;
		}
		dfs(node);
	}
	done[current] = 1;
}

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

	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; i++) uf[i] = i;

	while (M--) {
		int x, y; char c; cin >> x >> c >> y;
		x++; y++;
		if (c == '=') {
			x = findf(x), y = findf(y);
			uf[y] = x;
		}
		else queries.push_back({ x,y });
	}

	for (auto q : queries) {
		int x = findf(q.first), y = findf(q.second);
		G[x].push_back(y);
	}

	for (int i = 1; i <= N; i++) sort(G[i].begin(), G[i].end());

	int num = 1;
	for (int i = 1; i <= N; i++) {
		if (visited[i]) continue;
		dfs(i);
		num++;
	}

	if (chk) cout << "inconsistent";
	else cout << "consistent";
}

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

이번에 볼 문제는 백준 15701번 문제인 순서쌍이다.
문제는 아래 링크를 확인하자.

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

문제에서 나타내는 순서쌍의 개수는 결국 주어지는 N의 약수의 개수와 같다.

주어지는 N의 크기가 크므로, sqrt(N)범위까지 직접 나눠보는 것으로 모든 순서쌍을 찾을 수 있다.

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

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

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

	ll N; cin >> N;
	ll i = 1;
	int ans = 0;
	while (i * i <= N) {
		if (N % i == 0) {
			if (i * i == N) ans++;
			else ans += 2;
		}
		i++;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 20294번 문제인 에어컨 설치이다.
문제는 아래 링크를 확인하자.

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

각 방들을 꼭짓점으로 나타내고, 복도나 계단 등으로 연결된 두 꼭짓점 사이에 에지를 이으면 그래프를 하나 얻을 수 있다.

이 그래프는 좌표의 합이 홀수냐 짝수냐에 따라 집합을 나누면 이분그래프(bipartite graph)가 됨을 알 수 있다. 좌표합이 홀수인 점과 연결된 점은 좌표합이 짝수여야 하고 역도 성립하기 때문이다.

또한, 모든 방과 "복도, 계단"이 냉방이 되게끔 하는 최소한의 에어컨을 팔아야하므로 이 문제는 구한 이분그래프의 최소 버텍스 커버(minimum vertex cover)의 크기를 구하는 문제로 바꿀 수 있다.

이분그래프의 최소 버텍스 커버의 크기는 최대 이분매칭(maximum bipartite matching)의 크기와 같으므로, 이분매칭을 이용하여 답을 구하자.

단, 에지로 이어져있지 않은(vertex만 있는) 방은 모든 "복도, 계단"이 냉방이 되게끔 하는 최소 버텍스 커버에 포함되어있지 않은 vertex들이면서 에어컨을 설치해야하는 방이므로, 이러한 방들도 따로 세어주자.

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

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

struct point {
	int x, y, z;
};

bool adjacent(point p1, point p2) {
	int temp = abs(p1.x - p2.x) + abs(p1.y - p2.y) + abs(p1.z - p2.z);
	if (temp == 1) return 1;
	else return 0;
}

vector<point> ptL;
vector<point> ptR;

vector<int> G[1501];
int visited[1501];
int matching[1501];

int bipartite(int current) {
	if (visited[current]) return 0;
	visited[current] = 1;
	for (auto node : G[current]) {
		if (matching[node] == 0) {
			matching[node] = current;
			return 1;
		}
		if (bipartite(matching[node])) {
			matching[node] = current;
			return 1;
		}
	}
	return 0;
}

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

	int N; cin >> N;
	for (int i = 0; i < N;i++) {
		int x, y, z; cin >> x >> y >> z;
		point temp;
		temp.x = x, temp.y = y, temp.z = z;
		if ((x + y + z) & 1) ptL.push_back(temp);
		else ptR.push_back(temp);
	}

	int ans = 0;
	
	int L = ptL.size(), R = ptR.size();
	for (int r = 0; r < R; r++) {
		bool chk = 0;
		for (int l = 0; l < L; l++) {
			if (adjacent(ptL[l], ptR[r])) {
				G[l + 1].push_back(r + 1);
				chk = 1;
			}
		}
		if (chk) continue;
		ans++;
	}

	for (int i = 1; i <= L; i++) {
		if (G[i].empty()) {
			ans++;
			continue;
		}
		memset(visited, 0, sizeof(visited));
		ans += bipartite(i);
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 11670번 문제인 초등 수학이다.
문제는 아래 링크를 확인하자.

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

N(<=2500)개의 숫자쌍이 주어질 때, 이 숫자쌍들 사이에 +, -, *들을 적절히 넣어 각 계산식의 결과들이 다르게 만드는 문제이다.

나올 수 있는 세 가지 결과값들을 map 등을 이용하여 압축한 후 최대 이분매칭을 이용하여 문제를 해결하자.

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

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

vector<int> G[2501];
map<ll, int> mp;
ll queries[2501][2];

int visited[2501];
int matching[7501];
int bipartite(int current) {
	if (visited[current]) return 0;
	visited[current] = 1;
	for (auto node : G[current]) {
		if (matching[node] == 0) {
			matching[node] = current;
			return 1;
		}
		if (bipartite(matching[node])) {
			matching[node] = current;
			return 1;
		}
	}
	return 0;
}

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

	int idx = 1;
	int N; cin >> N;
	for (int i = 1;i <= N;i++) {
		ll x, y; cin >> x >> y;
		queries[i][0] = x, queries[i][1] = y;
		if (mp.find(x + y) == mp.end()) {
			mp.insert({ x + y,idx });
			idx++;
		}
		if (mp.find(x - y) == mp.end()) {
			mp.insert({ x - y,idx });
			idx++;
		}
		if (mp.find(x * y) == mp.end()) {
			mp.insert({ x * y,idx });
			idx++;
		}
		G[i].push_back(mp[x + y]);
		G[i].push_back(mp[x - y]);
		G[i].push_back(mp[x * y]);
	}

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

	if (ans < N) cout << "impossible";
	else {
		for (int i = 1; i <= N; i++) {
			ll x = queries[i][0], y = queries[i][1];
			if (i == matching[mp[x + y]]) {
				cout << x << " + " << y << " = " << x + y << '\n';
			}
			else if (i == matching[mp[x - y]]) {
				cout << x << " - " << y << " = " << x - y << '\n';
			}
			else {
				cout << x << " * " << y << " = " << x * y << '\n';
			}
		}
	}
}

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

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

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

이 문제는 2N자리수의 자연수 중 앞 N자리 수의 합과 뒤 N자리 수의 합이 같은 수의 개수를 구하는 문제이다.

이 경우의 수는 합이 각각 0~(9N)인 수들의 개수를 각각 제곱해서 더한 것과 같다는 것을 알 수 있다.

이를 dp를 이용하여 계산해주자.

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

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

ll ans[501];
ll dp[5001][501];

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

    for (int i = 0; i < 10; i++) dp[i][1] = 1;
    ans[1] = 10;

    for (int k = 2; k <= 500; k++) {
        int R = k * 10;
        for (int j = 0; j < 10; j++) {
            for (int i = j; i < R; i++) {
                dp[i][k] += dp[i - j][k - 1];
            }
        }
        for (int i = 0; i < R; i++) {
            dp[i][k] %= 1000000007;
            ans[k] += dp[i][k] * dp[i][k];
            ans[k] %= 1000000007;
        }
    }

    int T; cin >> T;
    for (int t = 1;t <= T;t++) {
        int x; cin >> x;
        cout << "Case #" << t << ": " << ans[x] << '\n';
    }
}

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

이번에 볼 문제는 백준 11695번 문제인 표 게임이다.
문제는 아래 링크를 확인하자.

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

표의 각 행에서 각 열의 숫자를 잘 생각하여 숫자를 빼는 것은 그냥 그 행의 모든 숫자를 모두 더해 하나의 돌무더기로 생각하는 님(Nim) 게임과 다를 것이 없다는 것을 확인하자.

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

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

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

	ll ans = 0;
	int R, C; cin >> R >> C;
	for (int r = 0; r < R; r++) {
		ll temp = 0;
		for (int c = 0; c < C; c++) {
			ll x; cin >> x;
			temp += x;
		}
		ans ^= temp;
	}

	if (ans == 0) cout << "ainta";
	else cout << "august14";
}