[백준][2661]좋은 수열

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

2661번: 좋은수열

 

완전 탐색 문제/DFS/백트래킹 이용

 

풀이

---

1.n 입력 받기

2.DFS 이용 수열 만들기

 2-1. 입력받은 수열 자리수가 n 이 되지 않더라도 좋은수열인지 체크 > 시간효율성 증가!

 2-2. n 만큼 탐색했을 때 걸러지지 않았다면 출력 

 

좋은수열 체크시 "임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다" 라고 문제의 조건에 있어서 난 처음에 n인 수열을 만든 후 좋은 수열을 체크했다.

그리고 첫번째 자리부터 1개 ~ n//2 개씩 단위로 좋은수열인지 나쁜 수열인지 체크했다. 시간이 너무 오래걸리고 탐색하는데 어떻게 접근해야할지 감이 오지 않았다.

아래 그림 처럼 비교해서 접근하려고 했는데 시간이 오래걸리고 구현방법이 구체화 되지 못함ㅠㅠ

 

해결

---

수열이 2개 이상 되면 좋은 수열인지 나쁜 수열인지 체크한다.

1. 111111 같은 경우 11에서 탐색이 종료되기 때문에 시간효율이 증가한다. > 백트래킹으로 돌아가기

2. 이미 탐색하고 다음단계로 오기 때문에 다음단계의 첫번째부터 그냥 탐색하면 됨!

 

 

 

코드

---

import sys
def dfs(level):
    global n
    global arr

    for i in range(1,(level//2)+1):
        if arr[-i:] == arr[-i*2:-i]:return -1

    if level == n:
        for i in arr:print(i,end='')
        return 0
    
    for i in range(1,4):
        arr.append(i)
        if dfs(level+1) == 0:
            return 0
        arr.pop()
    
if __name__ == "__main__":
    n = int(sys.stdin.readline())  
    arr = []
    dfs(0)