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

문제

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

풀이

n == 0 일 때, f(0) = 1, f(1) = 0

n == 1 일 때, f(0) = 0, f(1) = 1

n == 2 일 때, f(0) = 1, f(1) = 1

n == 3 일 때, f(0) = 1, f(1) = 2

n == 4 일 때, f(0) = 2, f(1) = 3

n == 5 일 때, f(0) = 3, f(1) = 5

n == 6 일 때, f(0) = 5, f(1) = 8

잘 보면 규칙을 발견할 수 있다 !

n>=2 일 때, f(0) = n-1의f(0)개수 + n-2의f(0)개수, f(1) = n-1의f(1)개수 + n-2의f(1)개수

따라서, f(0)의 개수를 담을 zero배열과 f(1)의 개수를 담을 one배열을 만들어주었다.

케이스별로 n-1, n-2 의 개수들을 더해주되, 반복되게 더해주는 부분을 제거하기 위해 flg 라는 변수를 만들어

그 값보다 n이 낮으면 이미 구해진 값이기 때문에 바로 출력, 아니라면 구한 후 출력하도록 구현했다.

소스코드

t = int(input())

zero = [0]*41
one = [0]*41
zero[0] = 1
one[1] = 1
flg = 2
for _ in range(t):
    n = int(input())
    nowflg = flg
    if n==0:
        print(1, 0, sep=' ')
        continue
    elif n==1:
        print(0, 1, sep=' ')
        continue
    elif n<flg:
        print(sum(zero[n-2:n]), sum(one[n-2:n]), sep=' ')
        continue
    for i in range(nowflg, n):
        zero[i] = zero[i-1]+zero[i-2]
        one[i] = one[i-1]+one[i-2]
        flg += 1
    print(sum(zero[n-2:n]), sum(one[n-2:n]), sep = ' ')