문제에서 너무나도 많은 것을 생략해버렸습니다.

역시 카카오의 수준은 남다릅니다.

덕분에 푸는데 오래걸렸습니다. 감사합니다.

먼저, 포화 이진 트리의 개념입니다.

포화 이진 트리라 함은, 부모 트리에 자식트리가 항상 2개가 있어야 하고,

높이 까지 싹다 일렬로 맞춘 트리를 말합니다.

그리고, 문제에서 높이는 살펴보는 순서에 상관없다는 완전 쓸데없는 소리를 해가지고,

더욱 헷갈리게 하였습니다. 진짜 뭐냐..

당연히 상관없죠.. 포화 이진 트리는 높이까지 싹다 맞춘 형태의 트리니까 말이죠.

십진수를 이진수로 변환하면, '1010101'과 같이 어떤 값이 나옵니다.

그리고, 이 값을 포화 이진 트리로 만들었을 때, 모순이 발생하는지 찾아보면 됩니다.

그런데, 포화 이진 트리는 부모 노드가 자식 노드를 반드시 2개 가지고 있음은 물론, 높이까지 전부 통일해야 한다고 했습니다.

그런데, 이진화 시킨 값으로 포화 트리를 반드시 만들 수 있는건 아닙니다.

그래서 우리는 이진화 시킨 값은 포화 트리로 만들 수 있게 높이를 통일 할 때 까지 앞에다가 더미 노드인 '0'을 추가합니다.

어차피 '0'은 앞에 아무리 추가해도, 이진수 값에 영향을 미치진 않으니까요.

포화 이진 트리의 노드의 갯수는 '2^높이 - 1' 입니다.

현재 이진수의 길이를 계산해서, 포화 이진 트리의 노드 길이에 해당되는 값 중에서, 가능한 최솟값을 되어야 합니다.

그러지 않으면, 높이가 맞질 않아 포화 이진 트리를 만들 수 없게 됩니다.

이해가 되셨나용?

예를 한 번 들어봅시다.

'11111111' 라는 이진수가 존재합니다.

종이에 저걸 포화 이진트리로 만들어 보려고 해보세요..

아마 만들어지지 않습니다.

왜냐하면, 포화 이진 트리의 노드 갯수에 충족하지 않거든요.

위의 이진수의 길이는 8이죠?

포화 이진 트리의 높이가 3인 경우 노드 갯수는 (2³ - 1 = 7) 7이 됩니다.
높이가 4인 경우의 노드 갯수는 (2⁴ - 1 = 15)가 됩니다.

이미 기존의 노드 갯수는 8개라 7개로 만들 수도 없는 노릇입니다.

그러면, 15개는 만들 수 있죠. 앞에다가 0을 7개 더 붙여주면 되니까요.

'000000011111111' 이라는 값으로 탐색하면 됩니다.

탐색은 간단합니다. 부모가 0일 때를 찾아서, 자식의 값이 1을 가지고 있는지를 확인하여 모순을 확인합니다.

부모가 0인데, 자식이 1을 가지고 있으면 안되겠죠?

애초부터 이진화 시킬 때, 0은 기존 트리에 더미노드로써 추가되는 값이니 말이죠.

루트 노드는 항상 저기 이진화 시킨 수에서 중간 지점이 루트가 되고,

그 기준으로 왼쪽은 좌측 자식, 오른쪽으로는 우측 자식이 됩니다.

그리고, 그 자식들도 dfs로 또 재귀로 보내버리면 될겁니다.

아주 간단합니다.

포화 이진 트리가, 높이를 반드시 맞춰줘야 한다는 개념만 알고있기만 한다면,

금방 풀 수 있습니다.

근데 카카오 문제는 출제자가 너무 괴짜인 것 같군요..

쓸데 없는 말들을 추가하여, 혼란을 야기하네용.

근데 틀린 말이 아니라서 뭐라 할 수도 없고 ㅋㅋ

수고하세용

20000