[코드트리 챌린지](3주차) 아름다운 수

 

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

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

 

실력진단 문제에서 계속 막혔던 재귀함수로 숫자 만드는 문제를 풀었다. 1, 22, 333, 4444를 하나의 셋트로 생각함

 

다 전역변수로 선언해서 함수 안에서 변경하면서 풀었다. 파라미터로 넘겨줄까도 생각했는데 그냥 귀찮아서 이렇게 했다.

 

<함수 동작 과정>

1. 길이를 검사한 후, 원하는 길이이면 카운트하고 리턴. 넘으면 그냥 리턴.

2. 1 추가한 뒤, 1로 돌아감

3. 마지막 원소의 숫자만큼 끝을 잘라냄

2'. 2, 2 추가한 뒤, 1로 돌아감

3'.

2''.

3''.

...

 

코드: 

global num, cnt, n
n = int(input())
num = []
cnt = 0


def beauti():
    global num, cnt, n
    if len(num) == n:
        cnt += 1
        return
    if len(num) > n: return
    
    num.append(1)
    beauti()
    num = num[:-num[-1]]
    
    for _ in range(2): num.append(2) 
    beauti()
    num = num[:-num[-1]]

    for _ in range(3): num.append(3) 
    beauti()
    num = num[:-num[-1]]

    for _ in range(4): num.append(4) 
    beauti()
    num = num[:-num[-1]]

    return

beauti()
print(cnt)

---

실력진단:

아 진짜 5초만 더있었어도 통과햇다진짜.

암튼 다음주차는 dfs, bfs 문제 풀어보겠음.