백준 1003번(피보나치 함수) 파이썬

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

1003번: 피보나치 함수

 

이 문제는 피보나치 함수의 0이 출력되는 횟수와 1이 출력 되는 횟수를 저장하여 뽑아내야 하는데 이 문제를 공책에 풀어보면서 규칙을 발견했다 0과 1의 출력 횟수가 피보나치 함수의 숫자와 동일하게 증가한다는 것을 알아냈다. 그래서 0과1의 횟수는 피보나치 함수의 정답과 동일한것이다. 그러나 한가지 다른점이 있다면 0의 갯수는 맨 앞에 1로 시작하는 것이다. 그래서 0의 횟수는 피보나치 함수의 수열 맨 앞에 1을 넣어 줘야 한다는 것이다 ex)0의 횟수=1,0,1,1,2,3,5,8......

1의 횟수 = 0,1,1,2,3,5,8.... 이므로 간단하게 피보나치 수열의 수들을 dp에 저장 해주면 된다.

 

import copy
import sys
n = int(sys.stdin.readline())
d = [0]*41
d[1] = 1
d[2] = 1
def fibo(x):
    if x == 1 or x == 2:
        return 1
    if x == 0:
        return 0
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

for i in range (n):
    x =int(sys.stdin.readline())
    fibo(x)
    d2 = copy.deepcopy(d) // 0의 횟수를 저장할 d2[]
    d2.insert(0,1)// 0의 횟수는 맨앞에 1을 추가로 넣어줘야한다.
    print(d2[x],d[x])

 

피보나치 수열을 dp에 적용하여 푸는 문제로 적당히 어려운 느낌의 문제였다. 풀면서 오랜만에 재밌는 느낌을 들었다. 그리고 풀었을때의 희열은 역시 좋았다