[코드트리] Backtracking - 아름다운 수

문제

코드트리 학습하기 - 알고리즘 입문 : Backtracking

• 아름다운 수 (Python)
  https://www.codetree.ai/missions/2/problems/beautiful-number/description

코드 구현

n = int(input())

arr = []

ans = 0
b_num = ''

def check_beautiful():
    c_2 = b_num.count('2')
    c_3 = b_num.count('3')
    c_4 = b_num.count('4')

    if (c_2 % 2 == 0 and c_3 % 3 == 0 and c_4 % 4 == 0):
        i = 0

        while(i < n):
            check_num = int(b_num[i])   # 검사해야하는 시작 번호
            for j in range(i, i + check_num):       # 해당 번호가 그 번호의 길이만큼 연속하는지 확인
                if(int(b_num[j]) != check_num):     # 연속으로 존재하지 않으면 False
                    return False
            i += check_num      # 그 다음 번호를 비교할 때에는 시작번호로 검사한 만큼 건너뛰고 검사를 시작해야함

    else:       # 2, 3, 4의 개수가 각각의 배수 갯수만큼 존재하지 않는다면 아름다운 수 X
        return False

    # 모든 검사를 통과하면 아름다운 수
    return True


def beautiful_num(num):     # 1,2,3,4를 n의 길이만큼 만들 수 있는 모든 숫자를 만드는 함수
    global b_num    # 아름다운 수를 담을 문자열
    global ans

    if (num == n):  # 종료 조건
        if (check_beautiful()):
            # arr.append(b_num)
            ans += 1
        return

    for i in range(1, 5):  # 1 ~ 4로만 구성
        b_num += str(i)
        beautiful_num(num + 1)
        b_num = b_num[:-1]

    return


## 메인 실행
beautiful_num(0)  # n의 길이만큼 아름다운 수의 후보를 만들어내기
# print(arr)
print(ans)

풀이

• 아름다운 수는 다음과 같다.
  • 1333221는 1이 1번, 3이 3번, 2가 2번 그리고 1이 1번 연속하여 나오므로 아름다운 수
  • 111, 22222222와 같은 수 역시 1이 1번 나온 것이 3번 반복되었고, 2가 2번 나온 것이 4번 반복되었다고 할 수 있기 때문에 아름다운 수

beautiful_num()

• 기본적인 Backtracking으로 수열을 생성하는 구조인 beautiful_num 함수를 기반으로 수행한다.
  • 해당 함수의 동작 부분은 1, 2, 3, 4의 숫자만 이용해서 n의 길이만큼 만들 수 있는 모든 숫자를 만들게 된다.
• 종료 조건으로는 n의 길이에 도달한 경우로 설정한 후, 만들어진 숫자가 아름다운 수에 해당하는지 판별하는 함수로 넘어간다.

check_beautiful()

• 아름다운 함수인지 판별하는 함수는 check_beautiful이다.
• 해당 함수는 1을 제외한 2, 3, 4가 각각 해당 배수의 개수만큼 들어있으면 검사를 시작한다.
  • 2, 3, 4가 각각의 배수 개수만큼 하나라도 존재하지 않으면 아름다운 수가 아니다.
  • 1은 몇개가 들어있어도 단독적으로 아름다운 수가 될 수 있으므로 조건에 필요없다.
• 검사를 해야하는 번호는 맨 첫번째 번호부터 시작하는데 해당 번호가 그 번호의 길이만큼 들어있는지 검사한다.
• ⭐️⭐️⭐️ 그 다음으로 검사해야하는 번호는 검사를 했던 숫자 번호의 길이 이후 인덱스부터 시작하면 된다.