[BaekJoon] 1003 피보나치 함수

▶ 문제

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

[출처 : https://www.acmicpc.net/problem/1003]

 

import sys
n = int(sys.stdin.readline().rstrip())
data = {i : 0 for i in range(41)}
# 숫자의 최대값이 40

result = [[0, 0] for i in range(41)]

result[0][0] = 1
result[1][1] = 1  

def fibo(n):
    if n == 0:        
        return 0
    elif n == 1:
        return 1
    elif data[n] > 0:
        return data[n]
    else:
        data[n] = fibo(n-1) + fibo(n-2)
        result[n][0], result[n][1] = result[n-1][0] + result[n-2][0], result[n-1][1] + result[n-2][1]
        return data[n]

for i in range(n):
    num = int(sys.stdin.readline().rstrip())

    fibo(num)
   
    sys.stdout.write(str(result[num][0]) +' '+ str(result[num][1]) +'\n')

 

▶ 문제 풀이

 

1. 제한시간이 짧은 편 => DP or 이분탐색 

2. 여기서는 DP가 적절하다고 판단

3. DP로 사용할 Dictionary와 List를 선언

    - Dictionary => 피보나치 수를 저장

    - List => 0과 1이 등장한 횟수 저장

    - List의 초기값 설정 => 0인경우 1인경우

4. fibo 재귀 함수를 통해 결과는 피보나치수를 리턴하면서 result리스트에 이전 값들에서 등장한 0과 1의 등장횟수를 누적 + 혹 이미 연산된 피보나치 수라면 저장된 값을 반환

5. 각각의 경우마다 출력