[백준] 31793. 공 굴리기

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

문제요약

• 깊이 N인 이진 포화 트리가 주어짐(N=60)
• 루트노드 1에서 공을 굴려서
  • 자식 노드의 루트 노드가 비어있는 쪽으로 공을 굴림
  • 둘다 비어있으면 공이 적은 서브트리로 공을 굴림
  • 그래도 안되면 루트 노드가 홀수면 오른쪽 먼저, 짝수면 왼쪽 먼저 공을 굴림
• 입력되는 순서의 공이 어디로 들어가는지 출력(최대 10^5개 주어짐)

접근법

• 잘 생각해보면 공은 왼쪽/오른쪽 번갈아서 들어감
  • 한쪽으로 공이 채워지면 공의 양이 많아지기 때문에 다음번에는 다른쪽으로 채워짐
  • 자식 노드의 루트노드가 비어있다는 의미도 결국 공의 적다는 의미
• 루트 R에서 공 K개가 들어온다면 왼쪽->오른쪽->왼쪽.... 을 반복하다가 어느 한 쪽으로 공이 들어갈 것임
• 그러면 새로운 루트 R에서 공 K/2개가 들어오는 새로운 문제가 됨
• 여기서 루트 R의 홀짝 여부와, K의 홀짝 여부에 따라 세부 내용이 달라질 수 있음
• ${f(R(루트노드), K(공의 개수), N(깊이)) = f(R'(자식 노드중 하나), {K \over 2} (or {K \over 2} + 1), {N \over2})}$