1003번 백준

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

1003번: 피보나치 함수

from sys import stdin

for t in range(int(stdin.readline())):
    n = int(stdin.readline())
    if not n:
        print(1, 0)
    else:
        l1, l2 = 0, 1
        for _ in range(n-1):
            l1, l2 = l2, l1+l2
        print(l1, l2)

피보나치 함수를 전개할 때 fib(0) 또는 fib(1)의 개수를 구하는 문제이다. (단, fib(x)는 x에 대한 피보나치 함수)

피보나치 수열은 DP(다이나믹 프로그래밍)의 대표적인 문제로 쓰인다. 예를 들어 fib(4)의 값을 구한다고 생각하자. 이를 위해서는 fib(3), fib(2)의 값을 구해줘야하고, 또 그 값은 fib(n-1)과 fib(n-2)을 계속 구해줘야 하는 방식이여야 한다. 만약 fib(5), fib(10)을 이 방법처럼 구한다면? 컴퓨터도 머리 지끈(?)거리는 수많은 연산을 반복해야 한다. 그래서 쓰이는 알고리즘이 DP 알고리즘이다. 이 알고리즘은 계산했던 바로 전 값을 따로 기억하여, 그 다음 값을 구하는데 쓰이는 것이다. 만약 fib(9), fib(8)을 이전에 구해두고 어딘가에다 적어두었다면, fib(10)은 구해진 두 값만을 이용하여 구할 수 있는 것이다.

이 문제는 잘 보면 피보나치 수열이 2개가 돌아가고 있다. 자, 직접 피보나치 수열을 그려보자. 0과 1, 2는 무난하게 fib(0)과 fib(1)에 도달할 때의 값을 구할 수 있다. 그럼 fib(3)은? 딱 한번만 전개를 하면 fib(1)+fib(2)가 된다. 즉, fib(1)의 결과와 fib(2)의 결과를 더해주기만 하면 된다. fib(4), fib(5)도 반복해보면, 0의 개수는 피보나치 수열의 n-1번째항, 1은 n번째항이 되는 것을 확인할 수 있다.

이를 활용하면 피보나치 수열의 값을 2번 저장하지 않고, 연산도 절반으로 줄어들어 시간적으로, 공간적으로 효율적이게 계산할수 있다.