[python] 백준 2661 좋은수열

https://www.acmicpc.net/problem/2661

2661번: 좋은수열

 

문제해결

•  문자열을 잘라서 앞에 문자열과 겹치는 것이 있는지 확인하는 문제
• 겹치는 것이 있으면 바로 그만두고 다른 경우의 수 찾기
• for문이 많아 시간복잡도 걱정이 있었다. (사실 그래서 다른 분들의 코드를 많이 참고하였다.)
• 백트래킹의 전형적인 문제

CODE

import sys
input= sys.stdin.readline
n = int(input())
result = []

def check(result, cnt):
    for i in range(cnt):
        sliceTemp = result[i:]
        for j in range(1,len(sliceTemp)//2+1):
            if sliceTemp[:j]==sliceTemp[j:j+j]:
                return False
    return True

def BackTracking(cnt):
    if not check(result,cnt):
        return -1
    if cnt ==n:
        print(*result,sep='')
        return 1
    for i in range(1,4):
        result.append(i)
        if BackTracking(cnt+1) == 1:
            return 1
        result.pop()
        
BackTracking(0)