[BOJ] 좋은 수열

BOJ 2661 골드 4

import sys
from collections import deque
input = sys.stdin.readline

def isGood(x):
    for i in range(1,len(x)):
        if x[-i:] == x[-2*i:-i]:
            return False
    return True

target = int(input())
answer = ''
v = '1'
visited = set()
while len(v) < target:
    for i in ['1','2','3']:
        if i == v[-1]:
            continue
        if v + i not in visited and isGood(v+i):
            v = v + i
            visited.add(v)
            break
    else:
        v = v[:-1]

print(v)

bfs 를 이용하려고 했는데 시간초과가 났다.
그래서 일단 가능한 값 중 가장 작은 값을 골라나가면서 visited 에 방문한 것을 저장하고, 수열이 더 만들어지지 않는 상황이 생기면 v의 끝을 지워나갔다. 그 후에는 visited 에 존재하는 것은 skip 하므로 다른 값을 이용한 수열을 만들 수 있다.

isGood 은 좋은 수열인지 판단하는 함수이다. 가능한 부분수열의 크기를 i로 놓고 x의 끝을 비교한다. 새로운 것을 하나 붙일 때마다 isGood 함수를 호출하므로, 마지막 문자를 제외하면 모두 좋은 수열임을 전제로 한다.