[알고리즘][파이썬] 백준_10870번_피보나치 수 5

20보다 작거나 같은 자연수 또는 0이 주어질때 그 수(n) 번째에 해당하는 피보나치 수를 구해야 한다.

피보나치 수는 0, 1에서 부터 시작하는 데,

바로 앞 두 수의 합이다.

n이 10일때 10번째 피보나치 수는 55이다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

---

1차 시도

# for 반복문 이용(결과: 틀렸습니다)

n = int(input())
lst = [0, 1]

for i in range(n-1):
    rst = lst[i] + lst[i+1]
    lst.append(rst)
    
print(max(lst))

 

지문과 같이 10을 입력했을 때 55가 정확하게 나왔다.

하지만 0을 입력했을때 0이 출력되어야 하는데 위 코드에서는 1이 출력되었기 때문에 틀렸던 것이다.

---

2차 시도

# for 반복문 이용(결과: 맞았습니다!)
# 0과 1의 처리에 주의했다.

n = int(input())
lst = []

for i in range(n+1):
    if i <= 1:
        lst.append(i)
    else:
        rst = lst[i-1] + lst[i-2]
        lst.append(rst)
    
print(max(lst))

 

성공!

---

3차 시도

# 재귀함수 이용(결과: 맞았습니다!)

def fibo(n):
    if n <= 1:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

print(fibo(int(input())))

 

성공!

본 문제는 백준의 단계별 풀어보기에서 10단계 재귀에 해당한다.

따라서 재귀함수를 이용한 풀이도 진행했다.

---

해결한 방법

재귀함수(자기 자신을 호출하는 함수)를 이용한다면,

0과 1의 처리에 유념해야 한다.

[그림1]을 보면서 이해하자!

 

[그림1] n이 5일때 재귀함수 수행 과정

 

재귀함수를 이용한 3차 시도 코드를 실행하고 5를 입력하면,

fibo(5) 함수는 fibo(n-1) + fibo(n-2)식에 의해 [그림1]과 같이 작동한다.

n이 1이하 일때(n <= 1) n을 돌려주도록 조건문이 작성되어 있기때문에

n이 0 또는 1일때 재귀함수는 더 이상 자신을 호출하지 않는다.

조건문에 의해 fibo(1)은 1이기 때문에 이를 모두 더해 주면 5가 나온다.

조건문에 의해 fibo(0)은 0이니 더하나 마나~