백준2661) 좋은수열

• 백트래킹 문제이다.

• 푸는데 1시간 정도 걸렸다.. 줄여야겠다..

• 가장 작은 수를 리턴해야 되기 때문에 1을 시작으로 하면 된다.

• 작은 수부터 붙여나가기 때문에 길이가 만족되면 출력 후 종료하면 된다.

n =int(input())

answer = 1e100



def isOk(s):

    size = len(s)
    
    for i in range(2, size//2+1):
        if s[size-i:size]==s[size-2*i:size-i]:
            return False

    return True
    

def getSol(cur):
    global answer
    if len(cur)==n:
        print(cur)
        exit(0)

    for i in range(1, 4):
        if cur[-1]==str(i):continue
        next_cur = cur+str(i)
        if isOk(next_cur):
            getSol(next_cur)




getSol("1")


print(answer)