In an infinite binary tree: 무한한 크기의 이진트리에서 각노드는 반드시 두개의 자식노드(왼쪽 자식, 오른쪽 자식)를 가진다.

어떤 한 노드의 번호를 X라고 한다면 왼쪽 자식노드의 번호는 2·X 이다.

그리고 오른쪽 자식노드의 번호는 2·X+1이다. 루트 노드의 번호는 1이다.

루트를 시작으로 이진 트리를 순회할 때 각 단계에서 왼쪽 노드부터 가고 오른쪽 노드를 방문한 후에 잠시 멈춘다.

각 순회에서 'L', 'R' , 'P'를 다음과 같이 정의한다.

'L' : 왼쪽 노드로 이동한다.

'R' : 오른쪽 노드로 이동한다.

'P' : 잠시 멈춘다.

순회의 값은 노드의 마지막에 도달했을 때 의 노드의 번호이다.

예를 들자면 RPP순회의 값이 3이라면 LR순회의 값은 5가 된다.

순회의 집합은 문자 'L', 'R', 'P', '*‘로 표시한다. '*'는 패턴상에서 'L'이거나 'R'이거나 'P'로 대치될 수 있다.

예를 들자면 집합 L*R은 LLR이거나 LRR이거나 LPR이 될 수 있다.

집합 **은 LL, LR, LP, RL, RR, RP, PL, PR , PP 될 수 있다.

결론적으로 모든 순회집합의 값은 집합에서 나올 수 있는 모든 순회값들의 총합이다.

주어진 순회집합의 값을 계산하는 프로그램을 작성하라.

무한이진트리(SETNJA) timer 2s memory 128MB

무한이진트리(SETNJA) 2s 128MB