[1003] 피보나치 함수

1003번: 피보나치 함수

 

www.acmicpc.net

---

🤔 문제 설명

 

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

 

fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.

fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.

두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.

fibonacci(0)은 0을 출력하고, 0을 리턴한다.

fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.

첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.

fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

 

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

 

🤨 제한 사항

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다.

• 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

 

😀 입출력 예

입력	출력
3 0 1 3	1 0 0 1 1 2

 

👩‍🔧 사용 메서드 및 속성

sys.stdin.readline()	사용자로부터 한 줄의 입력을 받습니다.
split()	문자열을 나눠서 배열로 반환합니다.
append()	리스트 끝에 요소를 추가합니다.

 

👩‍🏫 어떻게 풀어요?

 

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

 

가끔 백준 문제 풀다보면 거슬리는 문제가 있지 않나요?

이 피보나치 문제가 그런 것인데, 하필 예제를 fibo(0), fibo(1), fibo(3)일 때로 넣어놔서 푸는 사람으로 하여금 "0" 과 "1"이 몇번 출력되는지 착각을 일으키게 합니다. 그래서 처음에는 "아니 뭐 이런 걸 문제로 내는거지?? 0은 한번이고 1은 1번 아니면 2번 밖에 안나올텐데" 라는 생각을 했습니다..... 

 

물론 당연하게도 그런 문제는 아닙니다. 이 문제는 동적 프로그래밍 기법을 이용해야지만 시간을 단축할 수 있는 문제입니다. 저 같은 경우에는 저 0과 1을 글로벌 변수로 선언해서 하나하나씩 다 더한 다음에 memo에 넣는 방법을 시도하려고 했다가 노트에 피보나치 수열을 그려보며 규칙성을 찾고, 코드를 전면 수정했습니다.

 

 

fib(5) 일때의 1과 0이 나오는 경우

피보나치 수열은 0과 1을 제외하고, 그 외의 값은 전값과 전전값의 덧셈으로 구할 수 있는 수열입니다.

 0, 1, 1, 2, 3, 5 .... 이런식으로요.

 

그걸 이 문제처럼 그래프로 표현하고 표현식으로 나타내면

fib(0) = 0이 1개, 1이 0개니까      [ 1, 0 ]

fib(1) = 0이 0개, 1이 1개니까     [ 0, 1 ]

fib(2) = 0이 1개, 1이 1개니까     [ 1, 1 ]

fib(3) = 0이 1개, 1이 2개니까     [ 1, 2 ]

fib(4) = 0이 2개, 1이 3개니까     [ 2, 3 ]

fib(5) = 0이 3개, 1이 5개니까     [ 3, 5 ]

 

이렇게 나오는 걸 볼 수 있습니다.

 

혹시 규칙성이 있는것을 눈치채셨나요?

1의 개수는 전값과 전전값의 덧셈과 같고, 0의 개수는 전값의 1의 개수와 같다는 사실!

fib(5) = fib(4) + fib(3) = 5이고, 0의 개수는 fib(4)의 1의 개수와 같네요!!

그렇다면 문제는 쉽게 해결할 수 있겠네요.

 

동적 프로그래밍 기법을 사용해 봅시다.

memo[] (메모이제이션)를 선언해주고 거기다가 미리 0과 1의 결과값을 저장해줍시다. 그 다음 하나의 fib()가 종료될 때 값을 저장해서 넣어주면, 다음에 같은 fib()를 진행할 때는 굳이 깊게 재귀를 하지 않아도 결과가 나오겠죠?

 

 

👾트리스티의 답

import sys
 
n = int(sys.stdin.readline().split()[0])
arr = []
memo = {0 : 0, 1 : 1}
 
def fibonacci(number) :
    global memo
    if number in memo :
        return memo[number]
    fib = fibonacci(number - 1) + fibonacci(number - 2)
    memo[number] = fib
    return fib
 
for _ in range(n) :
    cnt = int(sys.stdin.readline().split()[0])
    if cnt == 0 :
        arr.append([1, 0])
    else:
        arr.append([fibonacci(cnt - 1), fibonacci(cnt)])
 
for i in arr :
    print(i[0], i[1])

 

※ 잘못된 정보가 있거나 수정사항이 있다면 댓글로 남겨주세요!