Baekjoon / Back Tracking / 좋은 수열

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

2661번: 좋은수열

 

Solution

def back_tracking(idx):
    print('idx :', idx)
    for i in range(1, (idx//2) + 1):
        print(i)
        if s[-i:] == s[-2*i:-i]:
            print('back')
            return -1

    if idx == n:
        for i in range(n):
            print(s[i], end = '')
        return 0

    for i in range(1, 4):
        s.append(i)
        print(s)
        if back_tracking(idx+1) == 0:
            return 0
        s.pop()

if __name__ == "__main__":
    n = int(input())
    s = []
    back_tracking(0)

 

실행 결과 로그

idx : 0
[1]
idx : 1
[1, 1]
idx : 2
1
back
[1, 2]
idx : 2
1
[1, 2, 1]
idx : 3
1
[1, 2, 1, 1]
idx : 4
1
back
[1, 2, 1, 2]
idx : 4
1
2
back
[1, 2, 1, 3]
idx : 4
1
2
[1, 2, 1, 3, 1]
idx : 5
1
2
[1, 2, 1, 3, 1, 1]
idx : 6
1
back
[1, 2, 1, 3, 1, 2]
idx : 6
1
2
3
[1, 2, 1, 3, 1, 2, 1]
idx : 7
1
2
3
1213121