[Python - Backtracking] 2661 좋은 수열

📌 문제

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

 

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

📌 입력

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

📌 출력

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

📌 문제 풀이

👨‍🏫 접근

백트래킹을 사용해서 조건에 맞는 문자열을 찾는 문제이다.

 

문제의 조건이 있으며, 정해진 길이가 있어서 재귀를 통해서 반복해가며 문제를 풀면 될 것 같다는 생각으로 접근했다.

조건을 검사하는 것은 뒤에서부터 조사하면 된다. 왜냐하면, 우리는 수열을 만들 때, 뒤에서부터 수를 붙여나가기 때문에 뒤에서부터 좋은 수열인지 검사하는 것이 더 효율적이기 때문이다.

 

검사는 2, 4, 6, 8 이렇게 짝수로 늘려나가면서 검사하며, 검사할 문자열을 반으로 나누어서 그 둘이 같은지 검사하여 조건을 확인할 수 있다.

👨‍🏫 문제 풀이

📄 전체 코드

def make_nums(nums, top, length):
    # 종료 조건
    if length == n:
        print(nums)
        exit()

    for i in range(1, 4):
        if i != top:
            if is_valid(nums + str(i)):
                make_nums(nums + str(i), i, length + 1)


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


n = int(input())
make_nums("", None, 0)

📄 준비

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


n = int(input())
make_nums("", None, 0)

유효한지 검사하는 함수를 만들었다.

 

검사 방법은, 총 문자열의 길이를 2로 나누어 문자열을 모두 검사한다. 검사는 [-2 * i: -1 * i]의 범위와 [-1 * i:] 범위의 문자열을 비교해서 같지 않은 경우에만 재귀를 진행하도록 한다.

📄 풀이

def make_nums(nums, top, length):
    # 종료 조건
    if length == n:
        print(nums)
        exit()

    for i in range(1, 4):
        if i != top:
            if is_valid(nums + str(i)):
                make_nums(nums + str(i), i, length + 1)

유효하다면 계속해서 재귀를 진행하고, 다 구했으면 바로 출력하고 종료한다.

📌 총평

꽤 어려웠는데 혼자 힘으로 풀었다. 스도쿠 문제만 스스로 풀게 되면 백트래킹은 조금 할만 해질 것 같다.