BOJ 2661: 좋은수열 [Python 3]

오늘의 문제는 백트래킹 및 dfs를 이용한 문제인 좋은수열이다.

def goodCheck(arr):
    for i in range(1,len(arr)//2+1):
       if arr[len(arr)-i:len(arr)]==arr[len(arr)-2*i:len(arr)-i]:
           return False
    return True
def dfs(arr,idx):
    if idx==n:
        print(''.join(str(i) for i in arr))
        exit()
    for i in range(1,4):
        if goodCheck(arr+[i]):
            arr.append(i)
            dfs(arr,idx+1)
            arr.pop()
    
            
n=int(input())
dfs([],0)

직관적으로 문제를 풀면 된다.

1부터 3까지 넣어가면서, 해당 수열이 조건을 만족하면 계속 넣고, 만약 잘 안 된다면 pop을 시킨다.

 

개인적으로 나는 

 

print(''.join(str(i) for i in arr))
exit()

두 가지를 정리하고 싶었는데,

 

join을 할 때, list 안에 들어가 있는 element가 string이 아닌 int여서 바로 join이 안 된다.

그렇기에 list comprehension을 써서, 각자 string으로 만들어서 넣는 방법이 있다.

 

(아니면 전 줄에 map을 이용해서 type을 바꿔줘도 된다.)

 

그리고 수를 하나만 출력하고 프로그램을 끝내야 하는데,

단순히 exit()함수를 쓰면 바로 프로그램을 종료할 수 있다.