[14570번] 나무 위의 구슬

문제 출처 :

https://www.acmicpc.net/problem/14570

알고리즘 분석 :

문제 해결에 필요한 사항

1. 재귀

2. 규칙

이 문제는 k번째 구슬이 어떻게 떨어질 지 규칙을 찾아내면 풀 수 있는 문제이다.

k 제한이 10^18이기에 구슬을 하나씩 트리의 리프노드에 넣는 과정을 취하면 TLE는 자명하다.

규칙을 생각해보자.

들어가는 순서 :: 2번, 4번, 2번, 5번, 2번

예제에 의하면 2, 4, 2, 5, 2번 순으로 들어간다.

이 의미를 자세히 생각해보면, 홀수번째 구슬은 왼쪽으로 가고, 짝수번째 구슬은 오른쪽으로 가게 된다.

그리고 최종적으로 보면 5개의 구슬을 넣었을 때 왼쪽에 총 3개, 오른쪽에 총 2개가 흘렀음을 알 수 있다.

따라서 홀수번째 구슬을 찾을 때는 왼쪽에 k/2 + 1을 해주고, 짝수번째 구슬을 찾을 때는 오른쪽에 k/2를 해주면 된다.

마지막으로 생각해봐야 할 것은 리프 노드가 왼쪽 오른쪽 둘다 없다면 그 위치가 정답이 되고,

왼쪽만 없다면 오른쪽으로 강제적으로 흐르게 된다. 따라서 k의 감소가 없다.

마찬가지로 오른쪽만 없다면 왼쪽으로 강제적으로 흐르게 된다. k의 감소가 마찬가지로 없다.

위의 규칙을 생각하여 코딩을 재귀적으로 짠다면 해결 할 수 있다. 

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <memory.h>
 
using namespace std;
 
typedef struct _TREE_
{
    long long left;
    long long right;
}TREE;
 
TREE tree[200002];
int ans;
void dfs(int n, long long k)
{
    if (k % 2 == 1)
    {
        if (tree[n].left == -1 && tree[n].right == -1)
        {
            ans = n;
            printf("%lld", ans);
            exit(0);
        }
        else if (tree[n].left == -1)
            dfs(tree[n].right, k);
        else if (tree[n].right == -1)
            dfs(tree[n].left, k);
        else if (tree[n].left && tree[n].right)
            dfs(tree[n].left, k / 2 + 1);
    }
    else if (k % 2 == 0)
    {
        if (tree[n].left == -1 && tree[n].right == -1)
        {
            ans = n;
            printf("%lld", ans);
            exit(0);
        }
        else if (tree[n].right == -1)
            dfs(tree[n].left, k);
        else if (tree[n].left == -1)
            dfs(tree[n].right, k);
        else if (tree[n].left && tree[n].right)
            dfs(tree[n].right, k / 2);
    }
}
 
int main()
{
    int n;
    long long k;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int left, right;
        scanf("%d %d", &left, &right);
 
        tree[i].left = left;
        tree[i].right = right;
    }
 
    scanf("%lld", &k);
    dfs(1, k);
 
    printf("%d", ans);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>