[Codetree] 아름다운 수 Python

https://www.codetree.ai/missions/2/problems/beautiful-number/description

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

 

1. 풀이1

import sys
import copy


result = []
answer = []

num = [1, 2, 3, 4]

cnt = 0

n = int(input())


def is_beautiful(answer):
    i = 0

    # 인덱스가 길이보다 작을 때만
    while i < n :
		
        # 현재 위치에서 필요 개수만큼 지났을 때의 인덱스가 넘치는지 확인
        if i + answer[i] - 1 >= n:
            return False

        # 현 위치의 숫자가 있는 만큼 길이가 필요하니까
        for j in range(i, i+answer[i]):
            if answer[i] != answer[j]:
                return False

        i += answer[i]
        
    return True



def backtrack(dep):
    global cnt, n

    # 일정 길이만큼 있는지 확인
    if dep == n:
        if is_beautiful(answer):
            temp = copy.deepcopy(answer)
            result.append(temp)
            cnt += 1
        return

    for i in range(4):
        answer.append(num[i])
        backtrack(dep+1)
        answer.pop()

    
backtrack(0)

print(cnt)

 

2. 풀이2

import sys
import copy

input = sys.stdin.readline

result = []
answer = []
num = [1, 2, 3, 4]

n = int(input())


def backtrack(dep):
    global n

    if dep == n:
        temp = copy.deepcopy(answer)
        result.append(''.join(map(str, temp)))
        return

    for i in range(4):
        answer.append(num[i])
        backtrack(dep+1)
        answer.pop()

backtrack(0)


cnt = 0
for r in result:
    r = r.replace('4444', '*').replace('333', '*').replace('22', "*").replace('1', '*')
    if r in ['*'*i for i in range(1, n+1)]:
        cnt += 1

print(cnt)