[백준 1003번] 파이썬 - 피보나치 함수

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

# 조건

• 피보나치 함수는 f(n ) = f(n-1) + f(n-1)의 성질을 가진다.
• 정수 n이 주어졌을 때 0과 1이 몇 번 출력되는지 구하여라.

 

# 접근 방법

• 문제에 주어진대로 재귀를 이용하여 구해봤지만 역시나 시간초과.
• 메모이제이션을 이용해봐도 시간초과가 나게 되었다.
• 0과 1이 출력되는 횟수가 수가 증가함에 따라 각각 피보나치 함수와 동일하게 출력됨을 발견
• 따라서 dp table을 따로 만들어 준 후 입력 n에 대해 횟수를 출력시켜준다.

 

 

# 시간초과 코드

def fibo(n):
    global cnt0, cnt1
    # 0과 1의 값을 정의 해준다.
    if n == 0:
        cnt0 +=1
        return 0

    elif n == 1:
        cnt1+=1
        return 1
    else:
        # 2단계 전과 1단계 전의 값을 더해준다.
        return fibo(n-2) + fibo(n-1)


T = int(input())
for i in range(T):
    n = int(input())
    cnt0 = 0
    cnt1 = 0
    fibo(n)
    print(cnt0, cnt1)

 

 

# 통과 코드

t = int(input())  
  
for _ in range(t):  
	# 0은 1부터 시작할 때 1-0 2-1 3-1 4-2 와 같고
	# 1은 1부터 시작할 때 1-1 2-1 3-2 4-3이 된다.
    cnt_0 = [1, 0]  
    cnt_1 = [0, 1]  
    n = int(input())  
    if n > 1:  
        for i in range(n - 1): 
	        # 0은 1의 피보나치함수보다 1단계 이전과 같으므로 
	        # cnt_1의 마지막 항을 추가해주면된다.
	        # 1의 경우 2번째 이전 항 + 1번째 이전항  
            cnt_0.append(cnt_1[-1])  
            cnt_1.append(cnt_1[-2] + cnt_1[-1])  
  
    print(cnt_0[n], cnt_1[n])