[파이썬] 백준 1003 : 피보나치 함수

문제 출처

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

1003번: 피보나치 함수

* 체크 리스트

---

시간

1. 즉시 작성 가능
2. 1시간 이내
3. 1시간 이상
4. 하루 이상

이해도

1. 이해 완료
2. 복습 필요
3. 부분 이해
4. 이해 불가

체감 난이도

1. 최상
2. 상
3. 중
4. 하
5. 최하

---

문제

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

입력

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

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

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

---

방법 1 - 재귀 함수 활용

# 1번 방법 - 시간초과
import sys
T = int(sys.stdin.readline())
# 변수 입력
count_zero = 0
count_one = 0

# 피보나치 수열 함수
def fibonacci(N):
    global count_zero, count_one
    # N == 0 일 경우 count_zero에 1을 더한다.
    if N == 0:
        count_zero += 1
        return 0
    # N == 1 일 경우 count_one에 1을 더한다.
    elif N == 1:
        count_one += 1
        return 1
    # 재귀 함수를 활용해 피보나치 수열을 반환한다.
    else:
        return fibonacci(N-1) + fibonacci(N-2)
# T번 반복
for _ in range(T):
    # 피보나치 숫자 입력
    num1 = int(sys.stdin.readline())
    fibonacci(num1)
    print(count_zero, count_one)
    # 재활용을 위해 0으로 초기화 한다.
    count_zero = 0
    count_one = 0

해결 방법 1

피보나치수열을 재귀 함수로 만들어 N == 0과 N==1일 경우 각각 횟수를 1회 추가하여 출력하였다.

출력 후 0으로 초기화. 하지만 위 방법은 재귀를 사용하기 때문에 시간 초과가 남.

---

방법 2 - 출력값의 규칙 찾기

# 2번 방법 - 규칙 찾기
# 위 피보나치 식에 값을 1~9 까지 넣으보면 해당 값도 피보나치 수열을 따름을 알 수 있다.
# 반복 횟수 입력
T = int(input())
# T번 반복
for _ in range(T):
    # num 번째 피보나치 값
    num = int(input())
    # 시작값 선언
    count_zero = 1
    count_one = 0
    # 0일 경우
    if num == 0:
        print(count_zero, count_one)
    # 이외에
    else:
        # num번 반복
        for _ in range(num):
            # 현재 count_zero는 이전 counrt_one과 값이 같으며,
            # 현재 count_one의 값은 이전 'count_one and count_zero'의 합이다.
            count_zero, count_one = count_one, count_one + count_zero
        print(count_zero, count_one)

해결 방법2

위 사진은 '해결방법 1'의 T값에 10을 넣어 0~9까지 출력한 결과이다. 위 결과를 보면 N==0과 N==1에도 피보나치와 같은 규칙이 있다는 것을 알 수 있다. (이전 N==0과 N==1의 합은 count_one)

이를 코드로 풀어내면

count_zero, count_one = count_one, count_one + count_zero

이 된다. 한 줄에 두 가지 모두를 사용(, 콤마로 구분)해야 이전 값의 변화 없이 원하는 결과 값을 얻을 수 있다.

---

깃 허브 - 정리

https://github.com/justin-kim3000/Python_Algorithm/blob/main/DynamicProgramming/fibonacci(1003).py 

GitHub - justin-kim3000/Python_Algorithm: Study