[BOJ]14570 : 나무 위의 구슬(c++)

[문제] : https://www.acmicpc.net/problem/14570

[풀이]

문제의 핵심은 어느 노드를 잡든 항상 왼쪽자식과 오른쪽 자식에게 있는 구슬의 수가 같거나 왼쪽이 1개 더 많다는 것입니다. K가 홀수일때 왼쪽과 오른쪽의 구슬은 (K-1) / 2개로 같으므로 K/2 + 1 개의 구슬을 가지고 왼쪽노드로 이동합니다. K가 짝수일때는 왼쪽에 K/2, 오른쪽에 K/2 - 1 개의 구슬이 있으므로 K/2의 구슬을 가지고 오른쪽으로 이동합니다. 이런 방식으로 오른쪽과 왼쪽에 자식이 모두 없는 경우가 될때 까지 이동해야 됩니다. (오른쪽이나 왼쪽 둘 중 하나의 자식이 없을 경우에는 가지고 있는 구슬 그대로 자식이 있는 쪽으로 이동합니다)

[코드]

#include <iostream>
#include <vector>

using namespace std;

struct c {
	int left;
	int right;
};

vector<c> graph;
int ret;

void solve(int nodenum, long long num)
{
	if (graph[nodenum].left == -1 && graph[nodenum].right == -1)
	{
		ret = nodenum;
		return;
	}
	else if (graph[nodenum].left == -1)
	{
		solve(graph[nodenum].right, num);
	}
	else if (graph[nodenum].right == -1)
	{
		solve(graph[nodenum].left, num);
	}
	else if (num % 2 != 0)
	{
		solve(graph[nodenum].left, num / 2 + 1);
	}
	else
	{
		solve(graph[nodenum].right, num / 2);
	}

	return;
}



int main(void)
{
	int N;
	cin >> N;
	graph.resize(N + 1);
	int a, b;

	for (int i = 1; i <= N; ++i)
	{
		cin >> a >> b;
		graph[i].left = a;
		graph[i].right = b ;
	}

	long long k;
	cin >> k;

	solve(1, k);
	cout << ret;

}