코드 복사/붙여넣기 하는 당신이 아름답습니다.

14570 : 나무 위의 구슬

풀이

문제의 조건을 그대로 가져다 써보자.

모든 노드에 대해, 왼쪽 구슬의 수가 오른쪽 구슬의 수보다 크거나 같다.

n개의 구슬 중 n/2+n%2개는 왼쪽, n/2개는 오른쪽으로 떨어지게 된다.

종단 노드를 만날 때 까지 돌려보자~~

코드

#include <stdio.h>

struct hello { int l, r; } t[200001];

int main() {
	int n; long long k;
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d %d", &t[i].l, &t[i].r);
	scanf("%lld", &k);
	int cur = 1;
	while (1) {
		if (t[cur].l == -1 && t[cur].r == -1) break;
		else if (t[cur].l == -1) cur = t[cur].r;
		else if (t[cur].r == -1) cur = t[cur].l;
		else if (k & 1) cur = t[cur].l, k = k / 2 + 1;
		else cur = t[cur].r, k /= 2;
	}
	printf("%d", cur);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-05-31 12:11

Read more posts by this author