[백준] 1003번: 피보나치 함수

문제

피보나치 수열은 대표적인 DP 문제인데, 이 문제는 다른 메모이제이션 방법이 필요하다.
단지 수열의 결과를 내뱉어야 하는 게 아니라 수열에서 쓰인 basic 수의 개수가 필요하다.

최근에 푼 떡 먹는 호랑이와 유사한 것 같으면서도 다른 문제!

풀이 II

시간 초과

testCaseNum = int(input())

def fibo(n, z, o):
     if n==0:
         return (0, z+1, o)
     if n==1:
         return (1, z, o+1)
     num1, z1, o1 = fibo(n-1, z, o)
     num2, z2, o2 = fibo(n-2, z, o)
     return (num1+num2, z1+z2, o1+o2)
        

for _ in range(testCaseNum):
     num, z, o =  fibo(int(input()),0, 0)
     print(z, o)

n번째 피보나치 함수일 때의 n
zero의 개수 z,
one의 개수 o을 합친 튜플을 탑다운으로 재귀를 하였는데, 시간초과가 났다.

재귀가 문제인가 싶어서 메모이제이션을 도입하여 새로 풀었다.

풀이 II

30840KB 72ms

testCaseNum = int(input())

for _ in range(testCaseNum):
    n = int(input())
    count0 = [1, 0]
    count1 = [0, 1]

    for i in range(2, n+1):
        count0.append(count0[i-1]+count0[i-2])
        count1.append(count1[i-1]+count1[i-2])
    print(count0[n], count1[n])

앞으로 DP는 웬만해선 바텀업 메모이제이션으로 풀어야 겠다.

느낀 점

DP... 최애 문제였는데
이젠 아니다...

지금 풀고 있는... 수익도 도통 점화식을 못 찾겠다...

원래는 React보다 알고리즘이 더 재밌었는데
지금은 React가 훨씬 재밌다...
코딩테스트... 이게 맞나...

그냥 너무 슬퍼
멍청한 내 자신이 안쓰럽고 짜증나