14570번 나무 위의 구술

문제 설명

이번 문제는 트리에 구술을 밑의 규칙대로 떨어뜨릴 경우, k번째 구술이 멈추게 될 노드의 위치를 찾는 문제입니다.

규칙

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

 

문제 풀이

이번 문제는 규칙을 찾는 문제입니다.

문제의 규칙 중에 3-1 번 규칙을 보게 되면, 구술을 떨어뜨리는 규칙이 왼 -> 오 -> 왼 -> 오... 로 반복된다는 것을 알 수 있다.

즉, k가 홀수일 경우에는 왼쪽으로 짝수일 경우에는 오른쪽으로 구술이 떨어지게 된다.

 

노드의 레벨마다 k를 2로 나눈 몫으로 교체해야 되는데, 이 때 k가 홀수일 경우에는 추가적으로 1을 더해주어야 한다.

그 이유는 N이 10이고 k가 1일 경우를 생각해보자.

처음에 k는 1이므로 왼쪽으로 구술이 떨어지게 된다. 그리고 k를 2로 나눈 몫은 0이 된다. 그렇게 된다면, k는 짝수가 되게 되므로 다음부터는 오른쪽으로 떨어지게 된다.

그러므로 k가 홀수 일 경우에는 1을 더해줘서, 해당 숫자가 0이 되는 경우의 수를 방지해 주어야 한다. (이 규칙을 이해하지 못해 조금 오래 걸린 것 같다😅)

 

해결

위 문제를 풀 때 필요한 것은

- 구술이 떨어지는 방향에 대한 규칙을 캐치해야 한다는 것

- 트리에 대한 규칙이니까 노드의 레벨마다 주어진 값에 변화를 주어야 된다는 것

- k=1 일 경우와 같이 자신이 현재 세운 규칙에서 배제 되는 부분을 찾아 규칙에 포함시켜주어야 한다는 것

위 세 개 정도인 것 같습니다.

 

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

14570번: 나무 위의 구슬

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/14570.py