[백준] 8916. 이진 검색 트리

https://www.acmicpc.net/problem/8916
https://www.acmicpc.net/problem/8944

문제요약

• 주어진 순열로 이진 트리를 구성했을때
• 동일한 모양이 나오는 순열의 경우의 수 구하기

접근법

• 루트는 정해질 것임
• 루트가 정해지면 이후 입력되는 숫자는 왼쪽/오른쪽은 정해질 것임
  • 왼쪽/오른쪽으로 숫자들이 새로 입력이 되는 형태이기때문에 새로운 부분문제라고 볼 수 있음
  • 왼쪽/오른쪽은 입력되는 값에 따라 알아서 경우의 수를 처리할 수 있을 것임
  • 트리의 "모양새"에 따라 경우의 수가 정해질 것 같은 느낌
• 왼쪽/오른쪽의 경우의 수를 적절히 잘 판단했다고 했을때 현 시점에서 할 일은
• 숫자들을 어떻게 배치해볼까임
  • 루트는 정해짐
  • 왼쪽/오른쪽으로 갈 숫자들을 나열을 해봐야하는데
  • 빈 곳 중 어디 어디를 왼쪽 숫자로 채울지로 생각해볼 수 있음(물론 나열하는 것은 다른 일이지만, 공간은 정해볼 수 있음)
  • $_{(n-1)}C_r$
    • 트리를 구성할 숫자가 $n$개인 상태에서
    • 가장 앞은 루트로 넣을 숫자가 와야하므로 $n - 1$
    • 나머지 공간에서 왼쪽 숫자로 채울 $r$개를 고르는 경우의 수
  • 그리고 이렇게 배치된 숫자들은 각각 왼쪽 트리를 구성하는 경우의 수와 오른쪽 트리를 구성하는 경우의 수만큼 가능해 질 것임
  • $f(cur) = _{(n-1)}C_r * f(left) * f(right)$
• 주어진 입력으로 트리를 만들어보고, 재귀적으로 호출하면서 값을 구해봄