BOJ 17306 - 전쟁 중의 삶 (트라이, 완전이진트리)

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

 

<문제설명>

무한완전 이진트리가 주어지고 루트(1)부터 각 정점에 순서대로 번호가 매겨진다.

 

최대 25e4개의 정짐의 번호(2^50보다 작음)가 주어진다. 정점간의 경로 상에 포함되는 모든 정점의 수를 구하라

 

<풀이>

각 정점의 번호를 2진수로 나타내면 1에서부터 그 정점까지의 경로를 트라이로 표현할 수 있다.

 

각 정점마다 1에서부터 경로 상의 최대 정점 수는 50개이므로 트라이의 총 노드의 수는 최대 50n개이다.

 

트라이의 각 노드 u마다 u를 루트로하는 서브트리에 포함된 정점의 수(term==1인 정점의 수)를 d[u]라고 할 때, d[u]가 1이상 n미만인 경우 u는 경로상에 반드시 포함된다.

 

<코드>

#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;
typedef long long ll;
const int MAX = 25e4 + 4;

ll n, ans;

struct Trie {
	Trie* next[2];
	bool term;
	Trie() {
		term = false;
		for (int i = 0; i < 2; i++) next[i] = NULL;
	}
	~Trie() {
		for (int i = 0; i < 2; i++) if (!next[i]) delete next[i];
	}
	void insert(ll key) {
		ll k = 64 - __builtin_clzll(key); //key를 2진법으로 나타낼 경우 필요한 비트수
		k--;
		if (k == 0) {
			term = true;
			return;
		}
		k--;
		bool c = key>>k & 1;
		if (next[c] == NULL) next[c] = new Trie();
		next[c]->insert((1ll<<k) + key % (1ll << k));
	}
};

int makeAns(Trie * curr) {
	int ret = curr->term;
	for (int i = 0; i < 2; i++)
		if (curr->next[i] != NULL) ret += makeAns(curr->next[i]);
	if (1 <= ret && ret <= n - 1) ans++;
	return ret;
}

Trie* root = new Trie();
int main() {
	FAST; cin >> n;
	for (int i = 0; i < n; i++) {
		ll x; cin >> x;
		root->insert(x);
	}
	makeAns(root);
	cout << ans + 1 << '\n';
}

 

<생각>

(1)

insert에서 log2(key)를 사용하려 했으나 key가 너무 크기때문에 오차가 나는 듯 하다. 

for문으로 log함수를 대체하려 했으나 시간초과가 난다.

 

 gcc 내장함수인 clzll을 사용해서 로그의 기능을 대체했더니 통과가 됐다.

 

(2)

모든 입력의 lca를 찾아서, 모든 입력에서 출발하여 lca에서 끝나는 multisource bfs가 시간초과가 났다.

 

완전이진트리이므로 lca를 찾는데 O(50n~100n), multisource bfs O(~100n)으로 정해와 비슷한 시간복잡도라고 생각했지만, 통과되지 않는다 ㅜㅜ

 

typedef long long ll;
const int MAX = 25e4 + 4;

ll n, a[MAX], w,ans;
queue<ll> q;
unordered_map<ll, bool> chk;

int main() {
	FAST; cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];

	w = a[0];
	for (ll i = 1,du,dv,u,v; i < n; i++) { // w와 a[i]의 lca를 w로
		u = w, v = a[i];
		du = log2(u), dv = log2(v);
		if (du < dv) {
			swap(u, v);
			swap(du, dv);
		}
		while (du != dv) {
			u /= 2;
			du--;
		}

		while (u != v) {
			u /= 2;
			v /= 2;
		}
		w = u;
		if (w == 1) break;
	}

	for (int i = 0; i < n; i++) {
		q.push(a[i]);
		chk[a[i]] = 1;
	}

	while (!q.empty()) {
		ll v,u = q.front(); q.pop();
		v = u / 2;
		ans++;
		if (u == w) continue;
		if (!chk[v]) {
			chk[v] = 1;
			q.push(v);
		}
	}

	cout << ans << '\n';
}

 

(3)

심지어 제일 낮은 깊이에서부터 단순히 조금씩 올라가도록 하는 코드를 set으로 짜면 시간초과고, vector로짠 후에 정렬후 erase, unique하는 코드는 통과한다.

 

(4)

시간제한을 조금 완화하거나 n크기를 약간만 줄여줬으면 좋았을 것 같다.

 

(5)

완전이진트리에서 정점번호로 경로를 저장할 수 있다