BOJ 14570 나무 위의 구슬

www.acmicpc.net/problem/14570

14570번: 나무 위의 구슬

 

이것도 처음 봤을 때는 못풀었다. 아니, 각 상황에 따라서 구슬이 내려가는 위치가 다른데, k가 10^18이라고? 분할정복도 아니고, 트리dp인가?? 하다가 못풀었던 문제인데

 

이제보니 이렇게 쉬울수가 없다... 규칙을 잘 생각해 보면 답이 나온다.

 

각 노드에서 구슬은 왼쪽 또는 오른쪽을 선택한다.

이 규칙에 의해서, 모든 상황에서 자식의 구슬개수는 

1. 양쪽 자식의 자식의 구슬개수가 동일하거나

2. 왼쪽 자식의 구슬개수가 오른쪽 자식보다 1개 많더나

 

당연히 1일때는 왼쪽자식으로 내려가야 하고, 2일때는 오른쪽 자식으로 내려가야 한다.

그럼 이 자식들은 자신의 subtree에 구슬을 몇개나 가지고 있는가?

 

지금 내가 구슬 i개를 가지고 있다고 할 때, 

왼쪽자식은 i/2개 (i%2==0)또는 i/2+1개(i%2==1)

오른쪽 자식은 i/2개

를 가져야 한다.

 

이걸 이용해서 쭉 자식을 타고 내려가다가 더이상 자식이 없는 점을 만나면, 그녀석이 k번째 구슬이 멈추는 위치이다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n;
	cin >> n;
	vector<vector<int> > edge(n+1);
	for (int i = 1; i <= n; i++) {
		int a, b; cin >> a >> b;
		//실제로 존재하는 자식만 push
		if (a != -1)
			edge[i].push_back(a);
		if (b != -1)
			edge[i].push_back(b);
	}
	
	ll k; cin >> k;
	int now = 1;
	while (1) {
		//자식이 없는 노드라면?
		//해당 노드가 정답노드
		if (edge[now].empty()) {
			cout << now; return 0;
		}
		//자식이 하나뿐이라면?
		//구슬은 선택권이 없다
		if (edge[now].size() == 1) {
			now = edge[now][0];
			continue;
		}

		//구슬을 왼쪽자식 또는 오른쪽자식중 누구에게 보낼 것인가?
		//홀수개의 구슬을 분류해야 한다면 k번째 구슬은 왼쪽으로 간다.
		//또한 왼쪽자식 노드는 k/2 + 1개의 구슬을 분류해야 한다.
		//짝수개의 구슬을 분류해야 한다면 k번째 구슬은 오른쪽으로 간다.
		//또한 오른쪽자식 노드는 k/2개의 구슬을 분류해야 한다.
		if (k % 2) {
			k /= 2;
			k += 1;
			now = edge[now][0];
		}
		else {
			k /= 2;
			now = edge[now][1];
		}

	}


	return 0;
}

 

코드의 실행시간이 조금 느리게 나오는데, 원인이 뭔지 모르겠다.

push_back()이 그나마 의심가는데, 자식은 최대 2개이니 미리 2칸만 resize해놓고 써도 될 듯 하다