[코드트리,백트래킹] 아름다운 수

문제

https://www.codetree.ai/missions/2/problems/beautiful-number?&utm_source=clipboard&utm_medium=text

풀이

- 백트래킹의 기본은 종료조건. 종료조건으로는 (배열의) 길이인 경우가 많다. 

- 백트래킹을 잘 못해서 해설을 봤음 ㅠ 연습 좀 해야될거같다 종료 조건은 아는데 아름다운 수를 재귀로 어떻게 판단할지 모르겠음

- 연속하는 수의 시작 위치를 찾아내는 방법이다.

- 위치(i) + 그 위치의 연속하는 숫자(arr[i]) 를 하면 숫자 만큼 연속해야되기때문에 다음 연속하는 수의 시작위치를 의미한다!

n = int(input())

def is_beautiful(arr): # 연속하는 해당 숫자의 시작 위치를 찾기 
    i = 0
    while i < n:
        # 연속해서 해당 숫자만큼 나올 수 없으면 아름다운 수 X
        if i + arr[i] - 1 >= n:
            return False
        
        for j in range(i, i + arr[i]):
            if arr[i] != arr[j]:
                return False
        i += arr[i]

    return True

ans = 0
def dfs(arr):
    global ans
    
    if len(arr) == n:
        if is_beautiful(arr):
            ans += 1
        return

    for i in range(1, 5):
        arr.append(i)
        dfs(arr)
        arr.pop()

    return

dfs([])
print(ans)