p679 ( Dropping Balls )

FBT, 완전 이진 트리에 대하여 푸는 문제.

 

FBT의 모든 노드는 초기값이 false로 세팅되어있고, 공은 루트노드부터 떨어진다.

공이 거쳐간 노드는 값이 반전( false라면 true로, true라면 false로 ) 되며, false였다면 왼쪽으로 공이 떨어지고 true면 오른쪽으로 떨어진다.

 

트리의 높이와 공을 떨어뜨린 횟수가 주어졌을 때, 마지막에 떨어진 공이 위치하는 노드의 값을 출력하는 문제.

 

공은 리프노드까지 떨어진다.

 

 

 

풀이

 

문제에서 얻어옴.

 

위와 같은 트리에서 공을 떨어트릴 수 있는 기회는 총 8번이다. ( 리프노드까지 공이 떨어지므로 )

이를 숫자로 표현하여 다시 나타내보면 다음과 같다.

 

 

 

 

 

잘 보면 루트노드를 기준으로 왼쪽 서브트리는 모두 홀수의 순서값을 가지고, 오른쪽 서브트리는 짝수의 순서값을 가진다.

 

따라서, 떨어뜨린 공의 횟수가 짝수라면 오른쪽으로 이동해야한다.

 

 

만약 우측 서브트리로 공이 떨어졌다면 순서값은 2 6 4 8 에서 1 3 2 4가 된다.

즉, 순서값에 /2를 해주면 된다.

 

반대로 왼쪽 서브트리로 공이 떨어졌다면 순서값은 1 5 3 7 에서 1 3 2 4가 되어야하므로, 각 순서값에 i / 2를 한 값을 빼줘야한다.

 

 

#include<iostream>
using namespace std;
#pragma warning(disable:4996);

int Depth, i, repeat;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> repeat;

	while (repeat--) {
		cin >> Depth >> i;

		int idx = 1;
		Depth--;
		while (Depth--) {
			if (i % 2 == 1) {
				idx *= 2;
				i -= (i / 2);
			}
			else {
				idx = idx * 2 + 1;
				i /= 2;
			}
		}

		cout << idx << '\n';
	}
	cin >> repeat;

	return 0;
}