백준-좋은 수열

2580_스도쿠 문제 해결법을 알아보다가 backtracking 기법이 있다는 것을 알게 되었다.

대표적인 문제는 9663_N-Queen 문제가 있다. 두 문제 다 풀이하지 못했다..ㅠㅠ

이 좋은수열 문제도 부분수열 문자열 처리하는 알고리즘을 짜지 못해서 해당 부분만 참고했다.

일단 백트래킹이란, dfs에서 완전탐색으로 진행하지 않고 가능한 경우만 stack에 삽입해서 탐색함으로써

탐색의 시간을 크게 단축시키는 기법을 말한다.

중요한 점은 stack에 넣기 전에 가능한 후보인지 검사해야 한다는 점이다.

문제

좋은 수열

풀이

1. 문제조건 해석

   백트래킹을 이용한 dfs 문제이다.

   문자열 처리의 경우 새로 삽입한 문자의 인접 행렬만 체크하면 된다.

2. 알고리즘

   문자열이 가능한지 체크하는 함수와

   dfs하는 함수를 구별하여 코딩했다.

   가장 작은 값만 구하면 되므로, dfs에서 처음으로 종료조건 나온 결과가 답이다.

3. 코드

    def chknum(string):
    i = 1
    while i<=len(string)//2:
        if string[-2*i:-i] == string[-i:]:
            return False
        i+=1
    return True
   
    def dfs(cur, n):
        if len(cur) == n:
            print(cur)
            exit()
        if chknum(cur+'1'):
            dfs(cur+'1', n)
        if chknum(cur+'2'):
            dfs(cur+'2', n)
        if chknum(cur+'3'):
            dfs(cur+'3', n)
   
    n = int(input())
    dfs('', n)