BOJ 13912 외계 생물

이 문제는 외계 생물에게 번호를 매긴다고 되어있지만 결국 full binary tree에 부모의 번호를 자식의 번호보다 작게 매기는 경우의 수를 구하는 문제이다.

모든 경우를 다 해봐야 하는... dp같다. 하지만 dp로 어떻게 접근해야할 지 쉽게 떠오르지 않는다. 모든 경우를 다 해본다....
음 d[r][num] : root를 (서브)트리의 루트 노드인 노드 r에 번호 num을 매겼을 때, 번호를 매기는 경우의 수... 로 해도 문제가 좀 있다.
부모의 번호보다 자식의 번호가 커야 하는데, 이게 루트 노드부터 시작해서 그 자식들에게 번호를 매기는 식으로 내려가면 왼쪽 서브트리에서 어떻게 하냐에 따라 오른쪽 서브트리에 영향을 미친다. 즉, 왼쪽 서브트리에서 어떤 번호를 썼는지 알아야 오른쪽 서브트리에 배치할 수 있는 경우의 수를 구할 수 있다... 번호는 최대 2048-1 = 2047까지 있는데... 상태 dp를 할 수도 없고...어렵다.

일단 오늘은 접고 다음에 좀 더 고민하다가 풀이를 봐야겠다. 이 문제처럼 전혀 감이 안 오는 문제는 너무 오래 고민하지 말자. 대신 풀이를 보면 확실하게 내 것으로 만들고 정리하자.