[코드트리 조별과제] 아름다운 수

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

재귀에 젬병이던 나에게 개념 정리를 해주는 문제가 나타났다.

항상 마지막 return 할 때 값을 바꿔줄지, 값을 리턴할지

어떤 조건으로 이어갈지, 배열에 값을 추가하고 빼낼 때 어떤 순서로 해야 하는지 헷갈렸는데

 

이 문제를 통해 조금이나마 확실하게 알게 되었다.

사실 이 문제 해설을 한번 보고 다 닫은 다음에 다시 짜봤는데 연습이 되었다.

 

아름다운지 확인하는 부분에서 나는 같은 숫자가 나오는 전체 갯수를 세고 

그것이 그 숫자로 나머지 없이 나눠지는 지 확인했는데, 

해설을 보면 22222222의 경우 22 22 22 22 이렇게 나눠서 각각 확인했다.

코드는 해설이 더 간단했다.

 

재귀 부분에서 global total 이라고 선언해 주면 재귀를 돌더라도 값이 공유된다는 사실을 알았고,

이를 통해 계속 값을 누적해 나갈 수 있었다.

그리고 전위, 중위, 후위 탐색 처럼 재귀를 어디에 두느냐에 따라 조건을 만족시킬 수 있었다.

 

이점 유의해서 다음에도 화이팅!👏

import sys

n = int(sys.stdin.readline())
total = 0
num_arr = []


# 아름다운 지 확인
def is_beautiful(num_arr):
    pin_start = 0
    idx = 0
    while True:
        if pin_start + idx >= len(num_arr):
            break
        if num_arr[pin_start] == num_arr[pin_start + idx]:
            idx += 1
        else:
            if idx % num_arr[pin_start]:
                return False
            else:
                pin_start = pin_start + idx
                idx = 0
    if idx % num_arr[pin_start]:
        return False
    return True


# 재귀 부분

def recursion(count):
    global total
    if count == n:
        if is_beautiful(num_arr):
            total += 1
        return

    for i in range(1, 5):
        num_arr.append(i)
        recursion(count + 1)
        num_arr.pop()


recursion(0)
print(total)