모각코 2회차 - 1/13일, 19시~22시

목표

코드트리 Intermediate Low 과정

Chapter 2. Backtracking : 재귀 함수를 통해 원하는 조합과 순열을 만드는 법을 배우게 됩니다.

 

결과

 

K개 중에 1개를 N번 뽑기

K, N = map(int, input().split())

arr = []

# Write your code here!
def permutation(cnt):
    if cnt == N:
        for num in arr:
            print(num, end=' ')
        print()
        return
    
    for i in range(1, K + 1):
        arr.append(i)
        permutation(cnt + 1)
        arr.pop()

permutation(0)

 

아름다운 수

n = int(input())

ans = 0
arr = []

def is_beautiful(arr):
    idx = 0
    cur_num = 0

    while idx < len(arr):
        cur_num = arr[idx]
        if idx + cur_num > len(arr): # 수가 n자리보다 큰 경우
            return False
        for i in range(cur_num):
            if cur_num != arr[idx + i]:
                return False
        idx += cur_num
    return True

def beautiful_num(num):
    global ans  
    if len(arr) == n:
        if is_beautiful(arr):
            ans += 1
        return

    for i in range(1, 5):
        arr.append(i)
        beautiful_num(num + 1)
        arr.pop()

beautiful_num(0)
print(ans)