bright

def solution(n):
    answer = ''
    
    max_num = 3  # 해당 자리수에서 가장 큰 수, 즉 4444.... 
    cnt = 1 
    
    while n > max_num :
        cnt += 1 
        max_num += 3**cnt

    while n > 0 :
        if n > max_num - (max_num - max_num//3 +1 )//3 : 
            answer += '4'
            n -= 3**(cnt)
        elif n > max_num - ((max_num - max_num//3 +1)//3)*2 : 
            answer += '2'
            n -= 2*3**(cnt-1)
        else : 
            answer += '1'
            n -= 3**(cnt-1)

        max_num -= 3**cnt
        cnt -= 1 
    return answer

1. 분류 : 구현..?  

2. 풀이 방법 : 

1 자리 수 : 1 2 4 

2 자리 수 : 11 12 14 / 21 22 24 / 41 42 44 

3 자리 수 : 111 112 114 121 122 124 141 142 144 / ...  444 

n 자리 수의 갯수 : 3^n 

각 자리 수 별 가장 큰 수 ( 4로만 이루어진 수 ) : 3 + 3^2 + 3^3 .. 

step 1 )  내가 몇 자리 수 인지 인지하고 내 자리수에서 가장 큰 값을 찾는다. 

step 2 )  각 자리수의 숫자는 3 단위로 이루어 진다.  

            예를 들어, 2 자리 수인 경우에 상위 1/3 는 맨 앞자리가 4,  2/3 은 2, 마지막은 1 이다. 

            따라서, 자리별로 적절하게 빼 가면서 어떤 수가 올지 파악한다. 

def solution(n):
    
    dp = [0]*100001
    
    dp[1] = 1 
    dp[2] = 1 
    
    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2]
        
    answer = dp[n] % 1234567
    return answer