[백준] 1003번 피보나치 함수 / 파이썬(python)

# 문제 링크

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

# 관련 알고리즘 이론

jiwon-coding.tistory.com/35

동적 계획법 (다이나믹 프로그래밍, DP)

# Soultion(실패)

재귀를 이용하여 문제를 풀었으나, 시간이 초과하는 문제 발생

cnt_0 = 0
cnt_1 = 0
 
def fibo(n):
    # 전역변수
    global cnt_0
    global cnt_1 
 
    if n==0:
        cnt_0 +=1
        return 0
    elif n==1:
        cnt_1 +=1
        return 1
    else:
        return fibo(n-1)+fibo(n-2)
 
t = int(input())
 
for _ in range(t):
    n = int(input())
    fibo(n)
    print(cnt_0, cnt_1)
    cnt_0 = 0; cnt_1 = 0
    

1. 2. 0과 1이 출력된 갯수 파악을 위한 전역변수

4. 피보나치 함수 생성, 함수안에서 각각 0과 1을 출력하게되면 카운팅

 

# Soultion(성공)

시간초과 문제를 해결하기 위해,  0과 1의 규칙을 찾아서 문제해결

0의 갯수 = 이전 1의 갯수, 1의 갯수 = 이전 0+이전1 갯수

t = int(input())
 
for _ in range(t):
    cnt_0 = [1,0]
    cnt_1 = [0,1]
    n = int(input())
    if n>1:
        for i in range(n-1):
            cnt_0.append(cnt_1[-1])
            cnt_1.append(cnt_0[-2]+cnt_1[-1]) 
 
    print(cnt_0[n], cnt_1[n])

4. 5. 기본으로 0과 1일때 갯수를 초기화시키기

7. 0과 1인 경우는 이미 리스트에 있으므로 1보다 클 경우만 진행

9. 현재 0의 갯수는 이전 1의 갯수를 가져옴

10. 현재 1의 갯수는 이전 0의 갯수+이전 1의 갯수