백준 1003번 <피보나치 함수>

백준 알고리즘 1003번

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

1003번: 피보나치 함수

1003번

피보나치 함수를 호출했을 때 0과 1이 각각 몇 번 출력되는지 구한다.

 

입력으로 첫 줄에 테스트케이스의 개수 T가 주어지고 각 테스트케이스는 한 줄로 이루어져있고 N이 주어진다.

 

출력으로 각 테스트케이스마다 0과 1이 출력되는 횟수를 공백으로 구분하여 출력한다.

 

문제 해결

주어진 테스트케이스에서 가장 큰 케이스 max까지 0과 1이 출력되는 횟수를 구한다.

0이 출력되는 횟수를 저장하는 배열 zero와 1을 출력되는 횟수를 저장하는 배열 one 두 개를 만들어서 max까지 구한다.

 

피보나치(n)의 값을 피보나치(n-2)의 값과 피보나치(n-1)의 값을 더한 값이기 때문에

zero와 one 또한 n-2와 n-1의 값을 더해서 구하면 된다.

 

def main():
    test = int(input())
    a = []
    max = 0
    for i in range(test):
        k = int(input())
        a.append(k)
        if max < k:
            max = k
    zero = [0 for _ in range(max+1)]
    one = [0 for _ in range(max+1)]
    zero[0] = 1
    one[1] = 1
    for i in range(2, max+1):
        zero[i] = zero[i-2]+zero[i-1]
        one[i] = one[i-2]+one[i-1]
    for i in a:
        print(zero[i],  one[i])
main()