[코드트리] 아름다운 수 Python

# n 입력
n = int(input())

# is_beautiful(curr_num_list)
def is_beautiful(curr_num_list):
    
    # curr_cnt
    curr_cnt = 1

    # curr_num_list를 돌면서
    for i in range(n-1):
        
        # 다음 수와 같으면
        if curr_num_list[i] == curr_num_list[i+1]:
            # curr_cnt 올려줌
            curr_cnt += 1    
        
        # 다음 수와 다르면
        elif curr_num_list[i] != curr_num_list[i+1]:
            # curr_cnt를 현재 수로 나눴을 때 나누어 떨어지지 않으면
            if curr_cnt % curr_num_list[i]:
                # 실패
                return False
            # curr_cnt 초기화
            curr_cnt = 1
        
        # 마지막이면
        if i == n-2:
            # curr_cnt를 마지막 수로 나눴을 때 나누어 떨어지지 않으면
            if curr_cnt % curr_num_list[n-1]:
                # 실패
                return False

    # 다 통과하면 성공
    return True

# get_beautiful_num(curr_idx)
def get_beautiful_num(curr_idx):
    
    global cnt

    # 종료 조건
    if curr_idx == n + 1:
        # 아름다운 수이면,
        if is_beautiful(num_list):
            # cnt 올려주기
            cnt += 1
        # 종료
        return

    # 숫자 넣기
    for i in range(1, 5):
        num_list.append(i)
        get_beautiful_num(curr_idx + 1)
        num_list.pop()    
    
# 설계
# num_list
num_list = []
# cnt
cnt = 0
# get_beautiful_num
get_beautiful_num(1)

# 출력
# n이 1이면
if n == 1:
    print(1)
# 1이 아니면
else:
    print(cnt)