반응형
SMALL
나무 위의 구술
-
14570번 나무 위의 구술알고리즘 2023. 1. 3. 15:25
문제 설명 이번 문제는 트리에 구술을 밑의 규칙대로 떨어뜨릴 경우, k번째 구술이 멈추게 될 노드의 위치를 찾는 문제입니다. 규칙 현재 구슬이 놓인 노드의 자식이 없다면 그 자리에서 멈춘다. 1을 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 한 개라면 해당 자식 노드로 떨어진다. 1, 2를 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 두 개라면, 현재 노드의 왼쪽 서브트리에 담긴 모든 구슬의 수 오 -> 왼 -> 오... 로 반복된다는 것을 알 수 있다. 즉, k가 홀수일 경우에는 왼쪽으로 짝수일 경우에는 오른쪽으로 구술이 떨어지게 된다. 노드의 레벨마다 k를 2로 나눈 몫으로 교체해야 되는데, 이 때 k가 홀수일 경우에는 추가적으로 1을 더해주어야 한다. 그 이유는 N이..