풀이
문제의 조건을 그대로 가져다 써보자.
모든 노드에 대해, 왼쪽 구슬의 수가 오른쪽 구슬의 수보다 크거나 같다.
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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이