[백준 1003번] 피보나치 함수

 

# 어제 풀었던 동적 계획법을 좀 더 공부해보기 위해 동적계획법 문제를 찾아 가장 기본인 것같은 피보나치 함수 문제를 골라 풀어 보았다.

 

-- 처음 짠 코드 ( 시간 초과 )

n = int(input())

def fibonacci(x):
    if x==0:
        zero_one_dict[0] += 1
        return 0
    elif x==1:
        zero_one_dict[1] += 1
        return(1)
    else:
        return fibonacci(x-1) + fibonacci(x-2)

for _ in range(n):
    k = int(input()) # 입력받는 x값
    zero_one_dict = {0: 0, 1: 0}
    fibonacci(k)
    print(zero_one_dict[0], zero_one_dict[1])

백준 문제는 항상 예제에 맞게 코드를 짜고 제출을 해보면 시간 초과가 나온다. ㅡ,ㅡ

위의 코드는 우선 피보나치 함수를 만들어 주고 각각 0을 호출할 때와 1을 호출할 때 경우의 수를 구해줄 zero_one_dict 딕셔너리를 만들어주어 각각의 횟수를 구해주었다. ( 하지만 시간초과 ㅎㅎ )

 

딕셔너리를 수정하는데 시간이 많이는 것일까? 하고 global 전역변수를 사용해 계산을 바꿔 보았는데도 시간초과가 나왔다..

 

어디서 또 시간이 그렇게 많이 걸린것일까.. 

사실 동적 계획법 문제를 풀어보겠다고 마음먹고 풀었던 것 치고는 해당 방법을 사용하지는 않은 것 같다. 

 

** 규칙 발견 **

위에서 만든 코드로 n이 0일때부터 10일 때 까지 돌려보았는데 규칙을 발견하였다.

그것은 바로 n-1값에서의 1이 프린트되는 횟수가 n값에서의 0이 프린트되는 횟수와 같다는 것!!

 

예를들어

* 0일때

1 0

* 1일때

0 1

* 2일때

1 1

* 3일때

1 2

* 4일때

2 3 

* 5일때

3 5

* 6일때

5 8

* 7일때

8 13

 

이런식으로 0이 프린트되는 횟수는 맨앞에 1을 제외하고는 n-1피보나치 수열의 형태를 띈다는 것을 확인할 수 있었다!!

 

-- 수정한 코드 ( 시간초과 )

T = int(input())

def fibonacci(x):
    if x==0:
        return 0
    elif x==1:
        return 1
    else:
        return fibonacci(x-1) + fibonacci(x-2)

for _ in range(T):
    n = int(input()) # 입력받는 x값
    if n == 0:
        print(1,0)
        continue
    print(fibonacci(n-1), fibonacci(n))

fibonacci함수를 2번이나 호출해서 그럴까.. 리스트에 저장해서 저장해둔 값을 2개 꺼내오는 식으로 만들어봐야겠다.

 

-- 정답 코드

T = int(input())

fibo = [0] + [1] + [0] * 39 # n은 0 ~ 40 이기 때문에 인덱스로 바로 파악하기 위해!

for i in range(2,41):
    fibo[i] = fibo[i-2] + fibo[i-1]


for _ in range(T):
    n = int(input())
    if n == 0:
        print(1,0)
        continue
    print(fibo[n-1], fibo[n])

저번 동적 계획법을 활용해 코드를 짰던 기억을 살려 코드를 만들어 보았다. 사실 빈 41개의 리스트를 만든다는 것 자체가 모든 경우의 수를 고려하지 못한다고 생각해 기존 코드의 범용성이 높다고는 생각하지만 뭐 어쩌겠는가..! 시간초과가 나지 않도록 주어진 조건을 활용해 풀 뿐 ㅠㅡㅠ 

 

 

 

오늘도 성공적으로 피보나치 수열을 만들어 주었다 ㅎ