[파이썬][백준 2661] 좋은 수열

www.acmicpc.net/problem/2661

2661번: 좋은수열

 

---

좋은 수열이 될 수 있는 과정 나열

 

1. 최소 값으로 만들기 위해 1, 2, 3 순으로 넣는다.

 

2. 반복 수열이 발생하면 맨 뒤의 수를 지우고 다음 수를 넣는다.

 

 

 

 

 

 

 

 

 

 

구상한 전략

- 1, 2, 3을 반복적으로 리스트 배열에 넣고, DFS를 실행하자.

- 이 때, 좋은 수열인지 확인하는 함수를 만들자(check)

특별히 고려한 점

1. check 함수를 만들 때 어떻게 비교를 시켜야하지?

(1) 1 ~ len(res)//2 의 범위를 갖는다.

 

(2) 빨강의 범위를 슬라이싱 해보자.

  - res = [1,2,3,4,5,6]에서 뒤의 3개를 선택하기 위해서는 res[-3], 즉 res[-i]

 

(3) 파랑의 범위를 슬라이싱 해보자.

  - res = [1,2,3,4,5,6]에서 뒤의 빨강 3개와 비교할 파랑 3개를 선택하기 위해서 정할 범위는

     -  빨강에서 -i까지 선택했으므로 res[:-i-1]까지 선택할 수 있다. 

     -  빨강에서 3개를 선택했으므로, 맨 뒤를 기준으로 3*2가 되는 지점을 선택하면 되겠다.

    -  결론적으로, 파랑색은 res[-i-i :-i-1]의 범위를 갖는다. 

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/codingtest/venv/input.txt", "rt")

def checker(a):
    for i in range(1, len(a)//2 + 1):
        if a[-i:] == a[-i-i:-i]:
            return False
    return True

def DFS(L):
    global res
    global flag

    if flag == 1:
        return

    if x == L:
        flag = 1
        for i in res:
            print(i, end = '')
        return

    else:
        for i in range(1, 4):
            res.append(i)
            if checker(res):
                DFS(L+1)
            res.pop(-1)

if __name__ == '__main__':
    flag = 0
    res = []
    x = int(input())
    DFS(0)