취미로 코딩하기

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

이번에 볼 문제는 백준 4792번 문제인 레드 블루 스패닝 트리이다.
문제는 아래 링크를 확인하자.

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

입력으로 연결그래프가 주어지므로, spanning tree가 포함되어있는 것은 자명하다.

노드가 N개인 그래프의 spanning tree는 N-1개의 edge를 가지게 된다.

이 문제를 해결하는 아이디어를 그대로 적는 대신, 풀이를 떠올릴 수 있는 관찰만을 기록해둘 것이다.

Kruskal(크루스칼) 알고리즘을 한 색깔의 에지들의 집합에 적용하면, 그 에지들을 이용하여 사이클이 없게끔 에지를 최대 몇 개 배치할 수 있는지 알 수 있다. 이 최대 개수의 배치에서 다른 그 색깔의 에지를 놓는다면 사이클이 생길 수밖에 없으므로, 이 배치를 포함하는 전체 그래프의 spanning tree의 나머지 에지는 다른 색깔의 에지로 채워지게 될 것이다. (그러한 spanning tree가 존재한다는 것은 조금 생각하면 알 수 있다.)

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

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

int R[1001];
int B[1001];

void init(int N) {
	for (int i = 1; i <= N; i++) {
		R[i] = B[i] = i;
	}
}
int findf_R(int x) {
	if (x == R[x]) return x;
	else return R[x] = findf_R(R[x]);
}

int findf_B(int x) {
	if (x == B[x]) return x;
	else return B[x] = findf_B(B[x]);
}

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

	int N, M, K; cin >> N >> M >> K;
	while (N != 0) {
		init(N);
		int cntR = 0, cntB = 0;
		
		while (M--) {
			char c; int f, t; cin >> c >> f >> t;
			if (c == 'R') {
				f = findf_R(f), t = findf_R(t);
				if (f == t) continue;
				cntR++;
				R[t] = f;
			}
			else {
				f = findf_B(f), t = findf_B(t);
				if (f == t) continue;
				cntB++;
				B[t] = f;
			}
		}

		if (N - 1 - cntR <= K && K <= cntB) cout << 1 << '\n';
		else cout << 0 << '\n';

		cin >> N >> M >> K;
	}
}

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

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

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

이 문제에서 서술하고 있는 게임은 보통 피보나치 님(Fibonacci nim)이라고 불리는 게임이다.

피보나치 님 게임의 필승전략은 주어진 동전의 개수 N을 제켄도르프 분해(Zeckendorf representation)하였을 때 나오는 피보나치 수 가운데 가장 작은 개수만큼의 동전을 가져가는 것이다. 제켄도르프 분해란 자연수를 연속하지 않은 피보나치 수의 합으로 나타내는 것을 의미하는데, 이러한 분해는 모든 자연수 N에 대하여 각각 유일하게 존재한다는 것이 제켄도르프 정리에 의해 보장된다. 이를 구현하면 주어진 문제를 해결할 수 있다.

피보나치 님 게임과 제켄도르프 분해에 대한 자세한 내용은 아래의 링크를 참고하자.

https://en.wikipedia.org/wiki/Fibonacci_nim

https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem

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

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

ll fib[77];

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

	fib[0] = 1, fib[1] = 2;
	for (int i = 2; i < 77; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	
	ll N; cin >> N;
	for (int i = 76; i >= 0; i--) {
		if (N == fib[i]) break;
		if (N > fib[i]) N -= fib[i];
	}
	cout << N;
}

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

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

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

이 문제에서는 주어진 rooted tree에서 어떤 한 노드와 그 노드를 루트로 하는 subtree를 삭제할 때 남는 트리의 리프노드의 개수를 세는 문제이다.

글쓴이는 입력을 받으면서 루트노드를 찾고 (남은) 트리를 탐색하면서 각 노드의 (삭제된 subtree의 루트노드가 아닌) 자식 노드의 개수를 세면서 개수가 0이면 답에 1을 더하는 방식으로 문제를 해결하였다.

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

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

vector<int> G[51];
int ans = 0;
int deleted;

void dfs(int current, int parent) {
	int childcnt = 0;
	for (auto node : G[current]) {
		if (node == parent || node == deleted) continue;
		childcnt++;
		dfs(node, current);
	}
	if (childcnt == 0) ans++;
}

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

	int root;
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (x == -1) {
			root = i;
			continue;
		}
		G[i].push_back(x);
		G[x].push_back(i);
	}

	cin >> deleted;

	if (deleted == root) cout << 0;
	else {
		dfs(root, -1);
		cout << ans;
	}
}

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

이번에 볼 문제는 백준 2647번 문제인 검은점과 하얀점 연결이다.
문제는 아래 링크를 확인하자.

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

주어진 문자열에서 검은점과 흰점의 개수가 같은 부분구간에 대한 부분문제를 생각할 수 있다.

이를 이용해 식을 잘 세우면 DP를 통해 구간의 높이와 거리합을 저장해가면서 재귀적으로 전체 구간의 최소 거리합을 구할 수 있다.

출력 또한 위 과정에서 역추적할 구간들을 미리 기록해두는 것으로 재귀적으로 가능하다.

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

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

int dp[101][101][6]; // dp[L][R][0/1] 0: L부터 R까지 최소거리, 1: 그때 높이 // 3~6: L1 R1 L2 R2
int prefixsum0[101];
int prefixsum1[101];

void func(int L, int R) {
	if (R == L + 1) {
		dp[L][R][0] = 3;
		dp[L][R][1] = 1;
		return;
	}

	int ret = 1000000007, ret_h, retL1, retR1, retL2, retR2;
	if (prefixsum0[R - 1] - prefixsum0[L] == prefixsum1[R - 1] - prefixsum1[L]) {
		if (dp[L + 1][R - 1][0] == 0) func(L + 1, R - 1);
		ret_h = dp[L + 1][R - 1][1] + 1;
		ret = dp[L + 1][R - 1][0] + 2 * ret_h + (R - L);
		retL1 = L, retR1 = R, retL2 = L + 1, retR2 = R - 1;
	}

	for (int r = L + 1; r < R; r += 2) {
		int l = r + 1;
		if (prefixsum0[r] - prefixsum0[L - 1] != prefixsum1[r] - prefixsum1[L - 1]) continue;

		if (dp[L][r][0] == 0) func(L, r);
		if (dp[l][R][0] == 0) func(l, R);
		int temp_h = max(dp[L][r][1], dp[l][R][1]);
		int temp = dp[L][r][0] + dp[l][R][0];
		if (ret > temp) {
			ret = temp, ret_h = temp_h, retL1 = L, retR1 = r, retL2 = l, retR2 = R;
		}
	}

	dp[L][R][0] = ret;
	dp[L][R][1] = ret_h;
	dp[L][R][2] = retL1;
	dp[L][R][3] = retR1;
	dp[L][R][4] = retL2;
	dp[L][R][5] = retR2;
}

void output(int L, int R) {
	if (R == L + 1) {
		cout << L << ' ' << R << '\n';
		return;
	}

	int L1 = dp[L][R][2], R1 = dp[L][R][3], L2 = dp[L][R][4], R2 = dp[L][R][5];

	if ((L1 == L && R1 == R)) {
		cout << L1 << ' ' << R1 << '\n';
		output(L2, R2);
	}
	else {
		output(L1, R1);
		output(L2, R2);
	}
}

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

	int N; cin >> N;
	string s; cin >> s;
	for (int i = 0; i < N; i++) {
		if (s[i] == '0') {
			prefixsum0[i + 1] = prefixsum0[i] + 1;
			prefixsum1[i + 1] = prefixsum1[i];
		}
		else {
			prefixsum1[i + 1] = prefixsum1[i] + 1;
			prefixsum0[i + 1] = prefixsum0[i];
		}
	}

	func(1, N);

	cout << dp[1][N][0] << '\n';
	output(1, N);
}

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

이번에 볼 문제는 백준 1213번 문제인 팰린드롬 만들기이다.
문제는 아래 링크를 확인하자.

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

팰린드롬(회문)은 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다.

팰린드롬 문자열은 위의 성질때문에, "길이가 홀수인 경우의 정가운데 들어가는 글자"를 제외하면 모든 글자는 짝수개 있어야 함을 알 수 있다.

따라서 A부터 Z까지의 문자의 개수를 각각 세고, 홀수개인 문자가 2개 이상이면 불가능, 그 외의 경우에는 A서부터 순서대로 절반개씩 찍어낸 뒤 홀수개 문자를 집어넣고 역순으로 찍어내면 된다.

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

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

int arr[128];

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

	string s; cin >> s;
	for (auto letter : s) arr[letter]++;
	
	int odd = 0; char oddletter = 0;
	for (int i = 0; i < 128; i++) {
		int cnt = arr[i];
		if (cnt & 1) {
			odd++;
			oddletter = i;
		}
	}

	if (odd > 1) cout << "I'm Sorry Hansoo";
	else {
		for (int i = 'A'; i <= 'Z'; i++) {
			for (int j = 0; j < arr[i] / 2; j++) {
				cout << char(i);
			}
		}
		if (odd) cout << char(oddletter);
		for (int i = 'Z'; i >= 'A'; i--) {
			for (int j = 0; j < arr[i] / 2; j++) {
				cout << char(i);
			}
		}
	}
}

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

이번에 볼 문제는 백준 1043번 문제인 거짓말이다.
문제는 아래 링크를 확인하자.

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

이 문제에서는 지민이가 진실을 말할 수 있는 파티의 수를 세야한다.

Disjoint Set 자료구조를 이용하면, (지민이를 제외한) 파티에서 만난 사람들끼리 만나고 다시 만나는 모임을 하나의 집합으로 간단하게 모을 수 있다. 그러면, 각 파티의 모임의 대표와 진실을 아는 사람을 한 사람씩 저장해두고 모든 파티를 disjoint set에 넣어 계산한 뒤 진실을 아는 사람과 연결되지 않은 파티의 수를 마지막으로 따로 세어 출력하는 것으로 이 문제를 해결할 수 있다.

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

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

int arr[51];
int query[51];
int findf(int x) {
	if (arr[x] == x) return x;
	else return arr[x] = findf(arr[x]);
}

void unionf(int x, int y) {
	x = findf(x), y = findf(y);
	if (x == y) return;
	arr[y] = x;
}

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

	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; i++) arr[i] = i;
	int T; cin >> T;
	if (T == 0) {
		cout << M;
		return 0;
	}

	T--;
	int truth; cin >> truth;
	while (T--) {
		int x; cin >> x;
		unionf(truth, x);
	}

	int MM = M;
	while (MM--) {
		int K, x; cin >> K >> x;
		K--; query[MM] = x;
		while (K--) {
			int y; cin >> y;
			unionf(x, y);
		}
	}

	int ans = 0;
	for (int i = 0; i < M; i++) {
		if (findf(query[i]) != findf(truth)) ans++;
	}

	cout << ans;
}