[골드 4] 백준 2661 - 좋은수열 (파이썬)

분류 : 백트래킹

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

풀이

이 문제는 숫자 1, 2, 3 으로만 이루어지는 수열이 있으며, 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열은 나쁜 수열이라고 한다.

좋은 수열은 인접한 두 개의 부분 수열이 동일하면 안된다. 즉 1212는 마지막 두자리 12가 반복되므로 나쁜 수열이다.

길이 N의 좋은 수열 중 사전순으로 가장 앞서는 수열을 찾아야한다.

def is_good(seq) :
    length = len(seq)
    for i in range(1, length // 2 + 1) :
        if seq[-i:] == seq[-2 * i : -i] :
            return False
    return True

이 함수는 현재 수열이 좋은 수열인지 판단한다.

i는 검사할 패턴의 길이, 최대 length // 2 까지만 확인하면 충분하다.

예를 들어서 123123에서는 뒤에서부터 길이 3까지의 패턴 123을 비교한다.

seq[-i:]는 마지막 i개의 문자, seq[-2*i:-i]는 그 앞 i개의 문자를 나타내며, 두부분이 같다면 반복되는 패턴이므로 나쁜수열이다.

반복이 없다면 좋은 수열을 나타낸다.

def dfs(seq) :
    global found
    if found : return
    if len(seq) == N :
        print(seq)
        found = True
        return 
    for digit in '123' :
        new_seq = seq + digit
        if is_good(new_seq) :
            dfs(new_seq)

현재 수열 seq를 기반으로 깊이우선탐색을 진행한다.

수열의 길이가 N이 되면 출력하고 종료하고, 숫자 1, 2, 3을 하나씩 붙여가면서 수열을 확장한다.

붙였을때 좋은 수열인지 검사 후 통과하면 재귀를 호출한다.

좀 어려운 문제인데 이게 어떻게 정답률이 50%..

코드

# 백준 2661 - 좋은수열
# 분류 : 백트래킹

N = int(input())

found = False

def is_good(seq) :
    length = len(seq)
    for i in range(1, length // 2 + 1) :
        if seq[-i:] == seq[-2 * i : -i] :
            return False
    return True

def dfs(seq) :
    global found
    if found : return
    if len(seq) == N :
        print(seq)
        found = True
        return 
    for digit in '123' :
        new_seq = seq + digit
        if is_good(new_seq) :
            dfs(new_seq)

dfs("")