[백준] 14570-나무 위의 구슬(C++)

문제링크:https://www.acmicpc.net/problem/14570

14570번: 나무 위의 구슬

 

간만에 털렸습니다...

우선 시뮬레이션 문제로 인식했습니다. 문제에서 요구하는 조건 그대로 이동하면서 결과값을 도출하게 끔 구현을 했습니다.

 

 

 

문제조건인 

1. 현재 구슬이 놓인 노드의 자식이 없다면 그 자리에서 멈춘다.
2. 1을 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 한 개라면 해당 자식 노드로 떨어진다.
3. 1, 2를 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 두 개라면,
   1. 현재 노드의 왼쪽 서브트리에 담긴 모든 구슬의 수 <= 오른쪽 서브트리에 담긴 모든 구슬의 수일 경우, 왼쪽 자식 노드로 떨어진다.
   2. 그 외의 경우에는 오른쪽 자식 노드로 떨어진다.
4. 1~3번의 조건을 다시 체크하고 되풀이한다.

를 생각하면서 구현한 답입니다.

 

#include <iostream>
using namespace std;

int n, u, v;
long long k;
int result = 0;
struct node {
	int left = 0;
	int right = 0;
};
node arr[200001];
int cnt[200001] = { 0 };
int left_cnt, right_cnt;

void add_cnt(int current,int direction) {
	
	if (arr[current].left == 0 && arr[current].left == 0) {
		if (direction == 0)
			left_cnt += cnt[current];
		else
			right_cnt += cnt[current];

		return;
	}
	if (arr[current].left != 0)  add_cnt(arr[current].left,direction);
	if (arr[current].right != 0)   add_cnt(arr[current].right, direction);

}

void action(int current,int i) {

	//1
	if (arr[current].left == 0 && arr[current].left == 0) {
		cnt[current]++;

		result = current;
		return;
	}
	//2
	else if ((arr[current].left != 0 && arr[current].right == 0)) action(arr[current].left,i);
	else if ((arr[current].left == 0 && arr[current].right != 0)) action(arr[current].right,i);
	//3
	else if (arr[current].left != 0 && arr[current].left != 0) {
		/*
		left_cnt = 0, right_cnt = 0;
		add_cnt(arr[current].left,0);
		add_cnt(arr[current].right,1);
		if(left_cnt <= right_cnt) action(arr[current].left);
		else action(arr[current].right);	
		*/

		if(i%2) action(arr[current].left,i/2 +1);
		else action(arr[current].right, i/2);
	}
}

int main() {

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> u >> v;
		if (u != -1 || v != -1) {
			arr[i].left = u;
			arr[i].right = v;
		}
	}

	cin >> k;

	for (int i = 1; i <= k; i++)
		action(1,i); //루트는 항상 1번 노드이다.

	cout << result << endl;
	
}

 

이러한 방식입니다. 문제가 많은 코드입니다. 

 

왜냐하면 1 ≤ K ≤ 10^18, 1 ≤ N ≤ 200000  이기 때문에 저렇게 무식한 시뮬레이션으로는 문제를 시간초과가 납니다.

 

규칙을 찾아야합니다. 

위와 같은 문제 규칙에서 2번, 4번, 2번, 5번, 2번 노드에 차례대로 떨어지게 됩니다. 

루트노드입장에서 생각해봅시다. k번째를 반복하며 인덱스가 홀수에서는 왼쪽 짝수에서는 오른쪽으로 이동합니다.

3의 입장에서도 보면 인덱스가 홀수에서는 왼쪽 짝수에서는 오른쪽으로 이동합니다. 

 

이러한 규칙이 있기 때문에 굳이 시뮬레이션할 필요가 없습니다.

즉 k번을 반복하는게 아니라, k번째만 확인해 답을 구할 수 있습니다.

 

 

정답코드입니다.

#include <iostream>
using namespace std;
struct node {
	int left, right;
};

node arr[200001];

int main() {
	int n; long long k;

	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i].left >> arr[i].right;

	cin >> k;

	int pos = 1; //루트 노드에서 시작
	while (1) {
		//1
		if (arr[pos].left == -1 && arr[pos].right == -1) break;
		//2
		else if (arr[pos].left == -1) pos = arr[pos].right; //왼쪽노드가 없음 -> 오른쪽으로 이동
		else if (arr[pos].right == -1) pos = arr[pos].left; //오른쪽노드가 없음 -> 왼쪽으로 이동
															//3
		else if (k % 2) {//1)조건 -> 홀수면 왼쪽으로 간다.
			pos = arr[pos].left, k = k / 2 + 1;
		}
		else { //2)조건 -> 짝수면 오른쪽으로 간다.
			pos = arr[pos].right, k /= 2;
		}
	}
	cout << pos << endl;

	return 0;
}

 

 

이중에서  아래 코드를 봅시다.

 

while (1) {
		//1
		if (arr[pos].left == -1 && arr[pos].right == -1) break;
		//2
		else if (arr[pos].left == -1) pos = arr[pos].right; //왼쪽노드가 없음 -> 오른쪽으로 이동
		else if (arr[pos].right == -1) pos = arr[pos].left; //오른쪽노드가 없음 -> 왼쪽으로 이동
															//3
		else if (k % 2) {//1)조건 -> 홀수면 왼쪽으로 간다.
			pos = arr[pos].left, k = k / 2 + 1;
		}
		else { //2)조건 -> 짝수면 오른쪽으로 간다.
			pos = arr[pos].right, k /= 2;
		}
	}

 

1,2번 조건은 쉽게 이해하실겁니다. 아래 코드에서 k%2와 k/2를 통해서 위치를 판별합니다. 

루트기준으로 k번째에서의 떨어지는 방향은 홀수면 왼쪽으로 짝수면 오른쪽으로 이동합니다. 

그아래 노드들도 위에서 설명한 규칙대로 이동하기 때문에 k값의 짝,홀수 를 변경해주는 것 입니다.