백준 2661 좋은 수열

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

2661번: 좋은수열

 

 

 

📌 해결순서

"인접한 두 부분수열"의 의미를 이해하는게 가장 중요한 문제였다.  인접한 이라는 말에 집중하지 않고 이런 풀이 과정을 생각했다.

1. 추가하려는 숫자 앞에 같은 숫자가 있으면 더이상 탐색하지 않고 return

2. 길이가 2부터 현재 길이까지의 부분수열을 만들어서 중복되는 부분수열이 있으면 더이상 탐색하지 않고 return

3. 백트래킹으로 완탐..

 

이렇게 생각하고 길이에 맞는 부분수열을 백트래킹 완탐으로 만들어주는 함수 하나를 더 만들고..탐색을 진행할지 말지 결정하는 함수를 또 만들고...혼자 키보드 두들겨가면서 삽질했다

 

친절하게 문제에서 인접한 부분수열을 보여줬는데도 혼자 무시하고 풀다가 굉장히 많은 시간을 썼다.. 진짜 문제 잘 읽자

 

만약 '1213121; 이라는 문자열이 있으면

1. lst[-1:]  lst[-2 : -1]  비교 -> 1 2

2. lst[-2:]  lst[-4 : -2]  비교 -> 21 31

3. lst[-3:]  lst[-6 : -3]  비교 -> 121 213

비교하려는 부분수열의 길이가 4가되려면 수열의 전체 길이가 4 * 2 = 8이 되어야 하기 때문에 길이가 3인 부분수열까지 비교할 수 있다.

 

여기서, 체크해야할 것은 1,2,3 순서대로 문자열에 추가하면서 비교하기 때문에 제일 처음 만들어지는 문자열이 가장 작은 

숫자일 것이다. 

입력 길이에 맞는 문자열을 만들고 프로그램이 아닌 함수만 종료 시키게 되면 뒤에 남아있는 dfs 함수들이 계속 입력 길이에 맞는 숫자를 생성하기 때문에 제일 처음 숫자를 출력하면 프로그램 자체를 종료 시켜야한다. -> sys.exit()

 

📌 코드

import sys
input = sys.stdin.readline


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


def dfs(num):
    if len(num) == n:
        print(num)
        # 제일처음 숫자를 출력하고 프로그램 자체를 종료 시켜야함, 종료코드 : exit()
        exit()
    # append 1, 2, 3
    # 숫자는 점점 증가하는 순서로 문자열에 추가하기 때문에 제일 처음 모든 조건을 만족하고 만들어지는 숫자가 제일 작다.
    for i in range(1, 4):
        if check(num + str(i)):
            dfs(num + str(i))


if __name__ == '__main__':
    n = int(input())
    dfs('1')