백준 9095번 파이썬 문제풀이(브루트 포스 - 수 이어 쓰기1)

코드

t = int(input())

array = [0, 1, 2, 4] # 1,2,3 일때 사용되는 횟수를 미리 배열에 선언

for i in range(4, 11): #문제에서 주어진 11까지 반복
    array.append(array[i - 3] + array[i - 2] + array[i - 1]) #i-3,i-2,i-1 번째에 있는 값들을 더한 값이 i번째에 등장한다.

for _ in range(t): #테스트 케이스 횟수만큼 돈다
    n = int(input())
    print(array[n])

-> 이문제는 간단히 점화식만 찾으면 된다. i-3 + i-2 + i -1 = i 번째와 같다는 것만 구한다면 쉽게 구할 수 있는 문제이다.

 

그러나 이문제를 재귀를 써서 브루트 포스로 풀어야 한다면 어떻게 풀 수 있을까.. 굉장히 좋은 코드가 있어서 공유한다. 머리속으로 아무리 돌려봐도 재귀는 이해하고 직접 코드를 구현하는것이 너무 어렵다..

 

재귀1

def solve(n):
    global cnt
    global k
    for i in arr:
        res.append(i)    
        if sum(res) == n:
            res.pop()
            cnt += 1
            break
        solve(n)
        res.pop()
    return cnt


T = int(input())
for _ in range(T):
    n = int(input())
    arr = [1, 2, 3]
    res = []
    cnt = 0
    print(solve(n))

 

재귀2

t = int(input())


def dfs(depth):
    global count

    if sum(out) > n:
        return

    if sum(out) == n:
        count += 1
        return

    for i in range(1, 4):
        out.append(i)
        dfs(depth + 1)
        out.pop()


for _ in range(t):
    n = int(input())
    count = 0
    out = []
    dfs(0)
    print(count)

-> 비슷한 코드이지만 위의 코드가 조금더 쉽게 느껴져서 올렸다.