"""
올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미한다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 된다. 괄호를 이리저리 움직이며 올바른 괄호를 찾던 A씨는 N개의 괄호쌍이 있을 때, 올바른 괄호를 만들 수 있는 경우의 수가 궁금해졌다.
괄호 쌍의 개수 N개가 주어졌을 때, 경우의 수를 반환하는 코드를 작성해라. 예를 들어 N = 1일 경우는 () 의 1가지만 존재하므로 1을 리턴하면 된다.3일 경우에는((())), (())(), ()(()), ()()(), (()()) 의 5가지가 존재하므로 5를 리턴하면 된다.

N = 1 : () -> 1
N = 2 : ()(), (()) -> 2
N = 3 : ()()(), (())(), ()(()), (()()), ((())) -> 5
"""

class node:
    left_node = None
    right_node = None



    def move_left(self):
	    self = self.left_node
    def move_right(self):
	    self = self.right_node

# left node check
def is_left_node(p_node):
    if p_node.left_node is None:
	    return False
    else : return True

# right node check
def is_right_node(p_node):
    if p_node.right_node is None:
	    return False
    else : return True

def recursive(p_node):
	if not is_left_node(p_node) :
		if N > left :
			left = left + 1
			recursive(node())

		else :
			if not is_right_node(p_node) :
				if left > right :
					right = right + 1
					recursive(node())
				else :
					return
			else :
				right = right + 1
				p_node = p_node.right_node
				recursive(p_node)
	else:
		left = left + 1
		pnode = p_node.left_node
		recursive(p_node)

# 가장 깊은 레벨의 경우의 수만 count !
def travel(p_node) :
	# depth가 가장 높은 노드만 찾는다는 것? 다른 관점에서 생각..
	# => 자식 노드가 없는 노드.. left, right 노드가 없는 노드
	if not is_left_node(p_node) :
		if not is_right_node(p_node) :
			total_count =  1 + total_count
		else :
			p_node = p_node.right_node
			travel(p_node)
	else :
		p_node = p_node.left_node
		travel(p_node)

total_count = 0

N = 3
left = 0
right = 0

# header생성
header_node = node()
left = left + 1

recursive(header_node)
travel(header_node)

print('입력 N 에 대한 경우의 수 : ')
print(total_count)