백준 2661번 -좋은수열(★★★ / O / 1) : Python

개요

• 풀이 시간 : 30~40분
• 시간 제한 : 1초
• 메모리 제한 : 128 MB
• 기출 : Olympiad 한국정보올림피아드 중등부 1번
• 링크 : https://www.acmicpc.net/problem/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들 사이에는 빈칸을 두지 않는다.

해결방법

문제 이해하기

일단 문제를 읽고 시뮬레이션을 해봤다. 1, 12, 121, 1213, 12131, 1213121까지는 그래도 할만했다. 하지만 1213121 다음에 1, 2, 3 모두 올 수가 없었다.

이렇듯 이것은 어떤 특정한 규칙이 있는 것이 아니라 DFS + 백트래킹을 사용해서 구현해야 한다는 것을 알게되었다.

알고리즘

전형적인 DFS + 백트래킹 문제이다. 이런류에 문제는 많이 풀어봤으므로 설명은 생략하도록 하겠다.

Python

내 코드

import sys
input = sys.stdin.readline

result = []

def check(result, addStr):
    temp = "".join(result) + addStr
    for i in range(1, len(temp) // 2 + 1):
        # print(temp[-2 * i : -1 * i])
        # print(temp[-1 * i :])

        if temp[-2 * i : -1 * i] == temp[-1 * i :]:
            return False

    return True


def dfsSearch():
    global result
    if len(result) == n:
        print("".join(result))
        exit()

    for i in range(1, 4):
        if check(result, str(i)):
            result.append(str(i))
            dfsSearch()
            result.pop()


if __name__ == "__main__":
    n = int(input())
    dfsSearch()

✍️ 한번에 성공했다. 다만 파이썬 마이너스 인덱싱을 초반에 실수하는 바람에 조금 시간이 걸렸다는 점 빼고는...