[백준 1003] 피보나치 구현

피보나치를 활용한 답 구하기 문제인 줄 알았는데 해결방법 자체가 피보나치였다.

답을 구하는 과정이 피보나치 수열로 나오기 때문이다. 

 

> 실패한 코드 1

def fibo(n):
    global n0, n1
    if n==0:
        n0 += 1
        return 0
    elif n==1:
        n1 += 1
        return 1
    return fibo(n-1) + fibo(n-2)

l = list(int(input()) for j in range(int(input())))
for i in l:
    n0, n1 = 0,0
    fibo(i)
    print(n0, n1)

처음 썼던 코드. 답은 맞았지만 시간초과로 실패했다.

위에서 말했듯이 재귀를 통해 피보나치를 구하는 과정에 0과 1이 출력되는 경우를 카운팅한 것이다.

문제를 직독직해해서 그대로 풀었다고 볼 수 있다. (응용력 0)

 

> 실패한 코드 2

def fibo(n,k):
    if n==0:
        return 0 if k==0 else 1
    elif n==1:
        return 1 if k==0 else 0
    else:
        return fibo(n-1,k) + fibo(n-2,k)

l = list(int(input()) for j in range(int(input())))
for i in l:
    print(fibo(i,0), fibo(i,1))

답 자체가 피보나치인 것을 알고 수정한 코드다. 똑같이 재귀함수를 이용했고 시간 초과로 실패했다.

 

> 성공 코드

def cnt(n):
    a0 = [1,0]
    a1 = [0,1]
    for i in range(2,n+1):
        a0.append(a0[i-1]+a0[i-2])
        a1.append(a1[i-1]+a1[i-2])
    return a0[n], a1[n]
for i in range(int(input())):
    print(*cnt(int(input())))

반은 구글링으로 베꼈다고 볼 수 있다.

이중 for문을 쓰는 게 더 깔끔했을 건데 반만 베껴서 생각을 못하고 또 함수를 이용했다.

이 간단한 방법을 왜 생각해내지 못한 건지... 문제를 더 풀어봐야겠다.