[백준/튼튼한기본기] 10870번: 피보나치수 5

[문제]

 

[내 코드]

a = int(input())
fn1 = 1
fn2 = 0

if a == 0:
    fn = fn2
elif a == 1:
    fn = fn1
else:
    for _ in range(a-1):
        fn = fn1 + fn2
        fn2 = fn1
        fn1 = fn 

print(fn)

- 처음에 fn2 = fn1 앞에 fn1 = fn 을 써서 계속 오류가 났다.. 이런 말도 안 되는 실수를..!!!!

- 분명히 더 깔끔한 방법이 있을 것 같은데, ...

- n이 2보다 작을 때는 어차피 fn = n 인데.. 왜 복잡하게 if문을 썼을까나.

- 머리가 터지는 줄 알았다. 살짝 자괴감 듦.;;

 

[개선안]

다른 코드를 보니까 내 코드가 얼마나 웃긴 건지 알겠다. 하하 ...

 

- 재귀함수

def fibo(n):
    if n < 2: 
        return n 
    return fibo(n-1) + fibo(n-2)
    
print(fibo(int(input())))

그러나 연산 시간이 매우 걸린다고 한다

 

- 명령형

a = 0
b = 1
c = 1
for _ in range(int(input())):
    a = b
    b = c
    c = a + b  
print(a)

range(0) 하면 에러 날 줄 알았는데 그렇지가 않구나 ... fn 을 구하기 전 fn-1과 fn-2를 세팅하는 방법을 썼다

 

- 동적 프로그래밍

n = int(input())
f = [0] * (n + 1)                       # n + 1 만큼 리스트 생성
def fibo(n):
    if(f[n]) != 0:                      # f안에 값이 존재한다면
        return f[n]                     # 재귀함수를 거치지 않고 그대로 출력

    if n < 2: 
        f[n] = n
        return f[n]
    else: 
        f[n] = fibo(n-1) + fibo(n-2)  # f[n]에 저장
    return f[n]
print(fibo(n))

(n+1) 길이만큼 되는 f 라는 리스트를 생성하고, 그 리스트에서 n번째 요소를 슬라이싱하여 출력한다