[백준] 2661번 - 좋은수열 (파이썬)

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

# 좋은수열
def choose_num(result, count):
    for i in range(1, count//2+1):
        if str(result)[count-i:] == str(result)[count-2*i:count-i]:
            return
    if count == N:
        print(result)
        exit(0)
    for i in range(1, 4):
        temp = result * 10 + i
        choose_num(temp, count+1)


N = int(input())
choose_num(0, 0)

 

백트랙킹

1. 1번부터 3번까지의 숫자를 총 N개를 골라서 result끝자리에 계속 더해준다

2. 만약 도중에 나쁜 수열에 걸리면 return

3. 좋은 수열이면서 제일 먼저 count가 N인 수열은 제일 작은 수이므로 print하고 종료

 

슬라이싱할때 살짝 귀찮았다