BOJ 28122 아이템

문제 링크입니다.

문제 요약

수직선 상에 $N$개의 아이템이 있습니다. 같은 위치에 여러 개의 아이템이 있을 수 있습니다.

아이템을 하나 골라 획득합니다. 그 뒤로 계속 아이템을 획득하는데, $i$를 지금까지 획득한 아이템의 개수라 하면, 다음으로 획득할 아이템은 마지막으로 획득한 아이템과의 거리가 $2^i$의 배수여야 합니다.

최대한 많은 아이템을 획득하세요.

풀이

$X$의 입력 범위를 보면, $10^{18} < 2^{60}$이므로 주어지는 아이템들의 위치를 60비트로 표현할 수 있음을 알 수 있습니다.

어떤 위치를 기준으로, $i$개의 아이템을 획득한 뒤 가지러 갈 수 있는 아이템들은 $i-1, i-2, \cdots, 0$개의 아이템을 획득한 뒤에도 가지러 갈 수 있습니다. 역은 성립하지 않고요. 아이템을 가지러 가지 못하게 되는 어떤 시점이 있을 텐데, 이는 두 아이템의 비트 표현이 처음으로 달라지는 지점을 넘어갔을 때임을 알 수 있습니다. 예를 들어, $8 = 1000{(2)}, 6=110{(2)}$이고, $2^1$의 자리에서 처음으로 두 수의 비트가 서로 다릅니다. 따라서 $1$번째 아이템을 획득한 때까지는 두 위치를 오갈 수 있지만, $2$번째 아이템을 획득한 이후로는 두 위치를 오갈 수 없습니다.

어떤 시점에서 집합이 쪼개진다는 논의로부터 트리 구조를 이용한다는 발상을 떠올릴 수 있습니다. 아이템의 위치를 작은 쪽 비트부터 순서대로 간선으로 취급해 이진 트리로 관리합시다. 우리가 선택할 수 있는 아이템의 집합은, 루트에서 출발해 아이템을 획득할 때마다 해당하는 방향으로 내려갔을 때의 서브트리에 포함되는 아이템의 집합과 대응됩니다.

이제 최대한 많은 아이템을 먹을 수 있는 경로를 찾아 봅시다. 트리를 따라 내려가면서, 선택할 수 있었지만 옆으로 지나친 서브트리에서 분기점 직전까지 획득해야 하는 아이템을 최대한 채워 줍니다. 그렇게 아이템을 선택하면서 닿을 수 있는 경로 길이의 최댓값을 구하면 답을 얻을 수 있습니다.

같은 위치에 있는 아이템의 처리에 유의해 주세요. 저는 시간/메모리 상 효율을 위해 같은 위치에 있는 아이템의 개수를 같이 저장하는 방식으로 트리의 높이를 60 언저리로 틀어막아 줬는데, 지금 생각해보니까 그냥 같은 아이템이 들어오면 아래로 한 칸씩만 늘리는 방식으로 짜도 상수 차이는 좀 나지만 괜찮은 코드가 나올 것 같네요.

총 시간 복잡도는 ${\cal O}(N \lg X)$입니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

struct Node{
	int l, r, cnt;
	Node(){
		l = r = -1;
		cnt = 0;
	}
};

struct Trie{
	vector<Node> v;
	int ans = 0;
	Trie(){
		v.push_back(Node());
	}
	void add(int now, ll X, int depth){
		v[now].cnt++;
		if(depth > 60) return;
		if(X&(1LL<<depth)){
			if(v[now].r == -1){
				v[now].r = v.size();
				v.push_back(Node());
			}
			add(v[now].r, X, depth+1);
		}
		else{
			if(v[now].l == -1){
				v[now].l = v.size();
				v.push_back(Node());
			}
			add(v[now].l, X, depth+1);
		}
	}
	int qry(int now, int path, int delta, int depth){
		if(depth > 60){
			return path+v[now].cnt-delta;
		}
		if(v[now].cnt <= delta) return path;
		path++;
		if(v[now].l < 0 && v[now].r < 0) return path;
		if(v[now].l >= 0 && v[now].r < 0) return qry(v[now].l, path, delta+1, depth+1);
		if(v[now].l < 0 && v[now].r >= 0) return qry(v[now].r, path, delta+1, depth+1);
		return max(qry(v[now].l, path, max(1, delta+1-v[v[now].r].cnt), depth+1),qry(v[now].r, path, max(1, delta+1-v[v[now].l].cnt), depth+1));
	}
} trie;

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n; while(n--){
		ll x; cin >> x; trie.add(0,x,0);
	}
	cout << trie.qry(0,0,0,0);
}