[ 백준 1003 - 피보나치 함수 ]

 

풀이

 

t=int(input())
a=[int(input())for _ in range(t)]

def f(n):
    if n == 1 : 
        return 0
    elif n == 2 : return 1
    fib_array = [0,1]
    for i in range(2,n+1):
        num = fib_array[i-1]+fib_array[i-2]
        fib_array.append(num)
    return fib_array[n-1]

for k in a:
    print(f(k),f(k+1))

 

• 처음에 단순히 피보나치 수열 찾아가는 과정을 거치며 0과 1이 나올 때마다 각각 +1씩 카운트 해주면 되겠다는 생각을 했다
• 하지만 그러려면 top-down 방식이 필요할 것이라 생각했는데 이는 연산 과정이 너무 오래 걸린다. ( top-down이 너무 오래 걸리기 때문에 배열을 만들어서 처음부터 하는 bottom-up 방식을 사용하는 것임
• 놓쳤던 부분 : 0과 1의 변화 추이를 보면 각각 피보나치 형태로 값이 증가한다는 것을 알 수가 있었다. 또한 도식표를 이용하여 살펴보면 왜 피보나치 꼴로 증가하는 지 알 수 있다.

0과 1의 변화 추이

	0	1
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	4

역시나 DP 문제에서는 규칙성을 찾는 것이 가장 중요하다. 규칙성이 안보인다면 구해야 하는 수를 쭉 나열해서 찾는 것도 최후의 방법이다.