[Algorithm] [백준] 1003 (Feat. 피보나치와 DP)

• 다이나믹 프로그래밍에는 재귀방식과 반복문 방식이 있다.

< DP 반복문 이용 >

# n이 0, 1, 2 일 때까지의 0과 1의 호출 횟수를 미리 저장
zero = [1, 0, 1]
one = [0, 1, 1]

def f(n):
    # 배열을 만들어서 값을 저장하므로 이미 구한 숫자를 또 구할 일이 없다
    # zero와 one 배열은 전역 변수이기 때문에 길이가 계속 바뀐다
    # 따라서 배열 길이로부터 n의 기준이 계속 바뀌어야 한다.
    length = len(zero)
    if n >= length:
        for i in range(length, n+1):
            zero.append(zero[i-1]+zero[i-2])
            one.append(one[i-1]+one[i-2])
    print(zero[n], one[n])

t = int(input())
for _ in range(t):
    n = int(input())
    f(n)

f(n) = f(n-1) + f(n-2) 개념을 적용하여,
💡 '피보나치 n에서 0과 1의 호출 횟수 = (피보나치 n-1에서 0과 1의 호출 횟수) + (피보나치 n-2에서 0과 1의 호출 횟수)'
로 배열에 추가하였다.

<틀린 처음 답안>

def f(n, cnt_zero, cnt_one):
    if n == 0:
        cnt_zero += 1
        return 0
    elif n == 1:
        cnt_one += 1
        return 1
    else:
        return f(n-1, cnt_zero, cnt_one) + f(n-2, cnt_zero, cnt_one)


t = int(input())
for _ in range(t):
    cnt_zero = 0
    cnt_one = 0
    n = int(input())
    a, b = f(n, cnt_zero, cnt_one)
    print(a, b)

피보나치라 하니 당연하게 재귀를 생각했지만 리턴값으로 cnt_zero와 cnt_one만 넘겨받을 수 없어서 헤매고 있었다.
하지만 이 문제는 재귀방식이 아니었던 것이다.