[BOJ/py] 2661 좋은수열

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

📝 문제

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

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

33
32121323
123123213
다음은 좋은 수열의 예이다.

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

💻 코드

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

def dfs(num, cnt):
    if cnt == N:
        print(num)
        exit()

    for i in range(1, 4):
        if check(num + str(i)):
            dfs(num + str(i), cnt + 1)

N = int(input())
dfs('1', 1)

📌 해결방법

1. 제일 작은 수열을 구하는 것이기 때문에 수열의 첫번째 원소는 '1'로 설정
2. 문자열 슬라이싱을 위하여 문자열로 설정하여 진행함
3. 1 ~ 3의 원소를 넣을때 check 함수를 통해 좋은 수열인지 판단한 후 재귀 진행함
4. 문자열의 길이가 N과 같아졌을 때 출력

✔ 느낀 점

로직을 짜는 부분과 재귀는 생각보다 빨리 구현했는데.... 문제는 check 함수에서 문자열 슬라이싱 하는 부분이었다..^^
슬라이싱 너무 헷갈려서 하나하나 디버그해보고 다른 코드를 조금 참고하여 완료했다....