파이썬 백준 2661번 : 좋은 수열

문제

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

 

 

🔮풀이

알고리즘

- 백트레킹 

 

1. 수열에 1,2,3을 순서대로 넣는다.

2. 넣을때마다 좋은 수열인지를 판단한다.

2-1. N개의 수로 이루어진 수열일때 좋은 수열인지 판별하기 위해서는  N+1//2(N>1)번의 탐색이 필요하다. (길이에 따라 0(len 1) 1 1 2 2 3 3...)

2-2. 좋은 수열을 판단할때는 인덱스 슬라이싱을 사용한다. 

3. 좋은 수열일 경우 다음 수에 1을 넣는다.

4. 1,2,3 모두 들어갈 수 없는 경우는 이전의 결과를 증가시킨다.

5. 수열의 길이가 N을 만족한다면 종료한다. 

 

import sys

def make_progression(i): #i는 추가할 번호 (1,2,3)
    i+=1 
    if i>3: #1,2,3이 다 안되면 이전 수를 증가시킴 1213121(다음에 1,2,3 다 안됨) ->1213122
        pre_index=progression.pop()
        make_progression(pre_index)
        return

    if len(progression)==N: #종료조건 : 수열의 완성
        print(''.join(map(str,progression)))
        return

    progression.append(i) #우선 수열에 넣는다!
    #나쁜 수열인지 확인
    if len(progression)!=1:
        for k in range(1,len(progression)+1//2):
            if progression[-k:] == progression[-(2*k):-k]:
                progression.pop() #나쁜 수열일때 그자리수를 하나 증가해서 넣기 ex) 1 2 1 2 -> 1 2 1 3
                make_progression(i)
                return

    #현재까지 좋은 수열!
    make_progression(0) #다음 자리수 넣기


N=int(sys.stdin.readline())
progression=[]
make_progression(0)

 

 

 

덧) 리스트 슬라이싱

nums=[1,2,3]

print(nums[-3:-1]) #1,2
print(nums[-3:]) #1,2,3
print(nums[1:-1]) #2
print(nums[-1:-1]) #빈리스트