[backjoon] 1003 피보나치 함수 (python)

문제 1003번: 피보나치 함수

Dynamic Programming

fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하는 문제

예제 입력

3
0
1
3

예제 출력

1 0
0 1
1 2

---

문제풀이

재귀함수로 풀려고 했는데 시간초과가 나서 다른 분들은 어떻게 코드를 작성했는지 참고하였다. 읽어 본 사이트

이 문제는 피보나치의 값이 아닌 fibonaaci(0)과 fibonacci(1)의 호출 횟수를 구하는 것이다.
원래의 fibonacci(n)을 구하기 위해서는 fibonacci(n-1)와 fibonacci(n-2)을 더해야 조건이 성립된다.
이 때 fibonacci(n)을 호출한다면, 실행되는 fibonacci(0)과 fibonacci(1)은
'fibonacci(n-1)의 0과 1 호출 횟수' + 'fibonacci(n-2)의 0과 1 호출 횟수'와 동일하다는 뜻이다!

zero = [1, 0, 1]
one = [0, 1, 1]

이 개념을 적용해서 문제를 풀어본다면, 숫자마다 0과 1의 호출 횟수를 저장할 리스트 zero, one을 생성해준다.

• 숫자가 0일 때 호출되는
  • 0은 1번
  • 1은 0번
• 숫자가 1일 때 호출되는
  • 0은 0번
  • 1은 1번
• 숫자가 2일 때 호출되는
  0은 1번
  1은 1번
  fibonacci(2) = fibonacci(1) + fibonacci(0)이기 때문

이렇게 0부터 2까지는 미리 배열을 만들어서 이보다 큰 숫자에서의 0과 1의 호출 횟수를 추가로 저장하면 된다.
배열을 만들어서 값을 저장하는 이유는 '다이나믹 프로그래밍'을 통해 이미 구한 숫자를 또다시 구하는 일이 없도록 하여 시간을 단축시키기 위함이다.

def fibonacci(num):
    length = len(zero)
    if num >= length:
        for i in range(length, num+1):
            zero.append(zero[i-1] + zero[i-2])
            one.append(one[i-1] + one[i-2])
    print('{} {}'.format(zero[num], one[num]))

코드를 보면 배열의 길이를 구해서, 배열의 길이보다 입력받은 숫자의 값이 크거나 같으면 반복문을 시작한다.

(그렇지 않으면 이미 배열에 저장되어 있는 값을 출력하면 되기 때문이다.)

위에서 알아본 피보나치를 구하는

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)개념을 적용하여,

'피보나치 n에서 0, 1의 호출횟수 = (피보나치 n - 1에서 0, 1 호출횟수) + (피보나치 n - 2에서 0, 1 호출횟수)'을 계산해서 새로운 값을 배열에 추가한다.

이처럼 배열에 추가하여 동일한 작업을 없애면 시간을 단축시킬 수 있다.

T = int(input())
    
for _ in range(T):
    fibonacci(int(input()))

그러고 나서 몇 번 반복할지를 변수 T에 입력받고 T번 만큼 피보나치 함수를 실행시킨다.
그럼 문제를 성공적으로 풀었음을 확인할 수 있다!

---

전체 코드

zero = [1, 0, 1]
one = [0, 1, 1]

def fibonacci(num):
    length = len(zero)
    if num >= length:
        for i in range(length, num+1):
            zero.append(zero[i-1] + zero[i-2])
            one.append(one[i-1] + one[i-2])
    print('{} {}'.format(zero[num], one[num]))

T = int(input())
    
for _ in range(T):
    fibonacci(int(input()))