[백준] 1003번 : 피보나치 함수

 

 

 

접근법

- n의 범위가 40보다 같거나 작기 때문에 시간 초과는 발생하지 않을 거라고 생각을 했다.

 

- 피보나치의 특성 상 n이 5라면 4와 3을 합친 값이 나오기 때문에 fibo(0)와 fibo(1) 각각의 0, 1 출력 횟수를 list로 만들어서 미리 넣어둔다. (fibo(0)의 경우 [1, 0], fibo(1)의 경우 [0, 1])

 

- n이 2보다 같거나 클 경우 i를 범위 (2, n + 1)만큼 돌려서 해당 i의 이전 값 2개의 0, 1 출력 횟수를 각각 더해준 후 list에 추가해준다.

 

- l[n][0], l[n][1]값을 출력해준다.

 

 

풀이

def fibo(n) :
    l = [[1, 0], [0, 1]]
    if n < 2:
        print(l[n][0], l[n][1])
    else :
        for i in range(2, n + 1) :
            z_cnt = l[i - 1][0] + l[i - 2][0]
            o_cnt = l[i - 1][1] + l[i - 2][1]
            l.append([z_cnt, o_cnt])
        print(l[n][0], l[n][1])

cnt = int(input())
for _ in range(cnt) :
    val = int(input())
    fibo(val)

 

 

 

결과