취미로 코딩하기

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

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

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

주어지는 rooted tree의 각 노드에 대하여 자손들 중 해당 노드의 가중치보다 높은 가중치를 갖는 노드의 개수를 구하는 문제이다.

주어지는 트리의 모든 자손 노드를 대상으로 하는 쿼리는 Euler Tour Technique을 이용해 노드의 번호를 재설정하고 각 노드의 자손의 수를 전처리한 다음 세그먼트트리를 이용해 쉽게 해결할 수 있다.

노드의 가중치가 큰 노드부터 차례대로 살펴보며 기존에 등장한 노드를 자손으로 얼마나 포함하고 있는지 계산 및 해당 노드를 세그먼트트리에 업데이트하는 것을 반복해 문제를 해결하자.

이를 구현할 때, 같은 가중치를 갖는 노드에 주의하자. Euler Tour Technique을 통해 새로 부여된 번호를 기준으로 큰 노드는 작은 노드의 조상이 절대 될 수 없음을 이용하면 특별한 예외처리 없이 정렬만 해도 문제를 충분히 해결할 수 있다.

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

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

int N;
int seg[262145];

void upd(int qI) {
	int L = 1, R = N, sI = 1;
	while (L < R) {
		seg[sI]++;
		int mid = (L + R) / 2;
		if (mid < qI) L = mid + 1, sI = sI * 2 + 1;
		else R = mid, sI = sI * 2;
	}
	seg[sI]++;
}

int qry(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return qry(L, (L + R) / 2, qL, qR, sI * 2) + qry((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

vector<int> G[100001];
int idx, dfi[100001], cnt[100001], inv[100001];
int dfs(int cur, int par) {
	int ret = 0;
	idx++;
	dfi[cur] = idx, inv[idx] = cur;

	for (auto& nxt : G[cur]) {
		if (nxt == par) continue;
		ret += dfs(nxt, cur);
	}
	cnt[dfi[cur]] = ret;
	return ret + 1;
}

pair<int, int> arr[100000];
int ans[100001];

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		arr[i] = make_pair(-x, i + 1);
	}

	for (int i = 2; i <= N; i++) {
		int x; cin >> x;
		G[i].emplace_back(x);
		G[x].emplace_back(i);
	}
	dfs(1, 1);

	for (int i = 0; i < N; i++) {
		arr[i].second = dfi[arr[i].second];
	}
	sort(arr, arr + N);

	for (int i = 0; i < N; i++) {
		int ii = arr[i].second;
		ans[inv[ii]] = qry(1, N, ii, ii + cnt[ii], 1);
		upd(ii);
	}

	for (int i = 1; i <= N; i++) cout << ans[i] << '\n';
}

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

이번에 볼 문제는 백준 27532번 문제인 시계 맞추기이다.
문제는 아래 링크를 확인하자.

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

먼저, 가능한 모든 R값은 mod 720에 대하여 720가지뿐임을 관찰하자. 이 각각의 R에 대해 시각이 주어진 것과 같이 나타나려면 시계가 몇 개인지 구하고 문제를 해결하자.

고정한 각 R값에 대하여 각 시계의 시각을 "시계를 처음 건 시점"을 기준으로 저장한다면 크기 720의 배열에 모든 시계를 간단히 저장할 수 있다.

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

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

int N;
int arr[1500];
int ans = 1000000007;
int visited[720];

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		arr[i] = (stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2))) % 720;
	}

	for (int R = 0; R < 720; R++) {
		memset(visited, 0, sizeof(visited));
		int cnt = 0;

		for (int i = 0; i < N; i++) {
			int t = arr[i] - (R * i) % 720;
			if (t < 0) t += 720;
			if (!visited[t]) visited[t] = 1, cnt++;
		}
		ans = min(ans, cnt);
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 13269번 문제인 쌓기나무이다.
문제는 아래 링크를 확인하자.

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

먼저 위에서 보았을 때 쌓기나무가 존재하는 각 칸에 가능한 많은 쌓기나무, 즉 해당 칸의 행과 열에서 볼 수 있는 쌓기나무 의 수 중 작은 값만큼의 쌓기나무를 놓아보자. 만약 이렇게 놓은 쌓기나무의 배치가 유효한 배치라면 이것이 문제에서 찾고자 하는 배치임은 자명하다. 더 많은 쌓기나무를 놓을 수 있는 방법이 없다는 것이 자명하기 때문이다.

이 배치가 유효하지 않은 경우, 그 이유는 다음과 같은 세 가지로 나눌 수 있다.

(1) 위에서 보았을 때 쌓기나무가 존재해야 하지만 위와 같은 과정에서 해당 칸에 놓은 쌓기나무의 수가 0개인 경우

이 경우 어떻게 하더라도 그 칸에 쌓기나무를 놓을 수 없으므로 -1을 출력해야 한다.

(2) 어떤 행에 그 행에서 볼 수 있어야 하는 쌓기나무의 수만큼 쌓기나무가 쌓인 칸이 없는 경우

이 경우 어떻게 하더라도 그 행에 원하는 개수의 쌓기나무를 놓을 수 있는 칸이 없으므로 -1을 출력해야 한다.

(3) 어떤 열에 그 열에서 볼 수 있어야 하는 쌓기나무의 수만큼 쌓기나무가 쌓인 칸이 없는 경우

2에서 행이 열로 바뀐 경우이다. 같은 이유로 -1을 출력해야 한다.

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

#include <iostream>
using namespace std;

int R, C;
int arr[500][500];
int hR[500], hC[500], mxR[500], mxC[500];

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

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

	for (int c = 0; c < C; c++) cin >> hC[c];
	for (int r = R - 1; r > -1; r--) cin >> hR[r];

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (arr[r][c]) {
				if (hR[r] == 0 || hC[c] == 0) {
					cout << -1;
					return 0;
				}
				arr[r][c] = min(hR[r], hC[c]);
				mxR[r] = max(mxR[r], arr[r][c]);
				mxC[c] = max(mxC[c], arr[r][c]);
			}
		}
	}

	for (int r = 0; r < R; r++) {
		if (mxR[r] != hR[r]) {
			cout << -1;
			return 0;
		}
	}
	for (int c = 0; c < C; c++) {
		if (mxC[c] != hC[c]) {
			cout << -1;
			return 0;
		}
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cout << arr[r][c] << ' ';
		}
		cout << '\n';
	}
}

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

이번에 볼 문제는 백준 10914번 문제인 Veni, vidi, vici이다.
문제는 아래 링크를 확인하자.

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

주어진 원철암호 단어들을 복호화하는 문제이다.

주어진 원철암호의 단어들은 앞에서부터 두 문자씩 끊어 해석할 수 있다. 두 문자가 나타내는 수의 합과 주어진 N을 이용해 원래의 문자를 계산하는 것으로 문제를 해결하자.

while문과 cin을 이용하면 주어지는 입력을 단어단위로 읽어 구현을 한결 편하게 할 수 있다.

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

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

int N, slen;
string s;

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

	cin >> N;
	while (cin >> s) {
		slen = s.length();
		for (int i = 0; i + 1 < slen; i += 2) {
			char c = ((s[i] - 'a') + (s[i + 1] - 'a') + 26 - N) % 26 + 'a';
			cout << c;
		}
		cout << ' ';
	}
}

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

이번에 볼 문제는 백준 28250번 문제인 이브, 프시케 그리고 푸른 MEX의 아내이다.
문제는 아래 링크를 확인하자.

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

크기 2의 multiset의 mex값은 0, 1, 2 세 가지 값만 나올 수 있음을 확인하자.

이 때 mex값이 1인 multiset은 0을 포함하지만 1을 포함하지 않는 경우이고, mex값이 2인 multiset은 0과 1을 모두 포함하는 경우임을 확인해 문제를 해결하자. '0을 포함하지만 1을 포함하지 않는 경우'에는 0을 두 개 고르는 경우도 포함됨에 유의하자. 

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

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

int N;
ll cnt0, cnt1, cnt2;
ll ans;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		if (x == 0) cnt0++;
		else if (x == 1) cnt1++;
		else cnt2++;
	}
	
	ans += cnt0 * (cnt0 - 1) / 2;
	ans += cnt0 * cnt2;
	ans += cnt0 * cnt1 * 2;

	cout << ans;
}

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

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

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

주어진 X-shaped level junction과 Y-shaped switch들을 먼저 바닥에 늘어놓고 다른 트랙을 이용해 이들을 이을 수 있는지를 판단하는 것으로 문제를 해결하자.

이 때, X-shaped level junction은 하나 추가될 때마다 이어야 할 끝점이 4개씩 늘어나고 Y-shaped switch는 하나 추가될 때마다 이어야 할 끝점이 3개씩 늘어난다. 한편, 각 끝점은 둘씩 짝지어 이을 수밖에 없으므로 끝점의 개수가 홀수인 경우 올바르게 트랙을 구성할 수 없다. 반면에 끝점의 개수가 짝수인 경우 "X-shaped level junction의 이웃한 두 끝점을 연결해 일반 레일처럼 사용하고 Y-shaped switch들을 일렬로 나열한 뒤 끝점을 하나씩 서로 이은 뒤 나머지를 아무렇게나 짝짓는 방법" 등으로 이들을 잇는 방법이 항상 존재하므로 항상 올바르게 트랙을 구성할 수 있다.

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

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

#include <iostream>
using namespace std;

int x;

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

	cin >> x >> x;
	if (x & 1) cout << "impossible";
	else cout << "possible";
}