[Seop's의 코드풀이] 백준 1788 피보나치 수의 확장 - python

이번에 풀어볼 문제는 백준 1788번인 피보나치 수의 확장이라는 문제이다.

 

문제를 보면 다음과 같이 설명 되어 있다.

 

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

1788번: 피보나치 수의 확장

 

 

 

우리가 익히 알던 피보나치 수는 0보다 큰 양의 정수만 정의된다.

본 문제에서는 음의 정수에도 피보나치 수를 확장 시킨 것이다.

완전히 새로울 것 같지만 몇단계만 거친다면 우리가 익히 알던 피보나치 수와 큰 차이가 없다는 것을 알 수 있다.

 

본 문제에서 진행하고 있는 것 처럼 음의 정수의 피보나치 수를 구해 보았고 이를 토대로

식을 작성해 보았다. 즉 우리가 봐왔던

f(n) = f(n-1) + f(n-2)

와 유사한 모습이지만 더하는 것이 아니라 빼는 것이 된다.

이렇게 빼기를 지속할 경우 음의 피보나치수의 부호가 계속 반전되는 모습을 볼 수 있다.

 

n	f(n)
0	0
-1	1
-2	-1
-3	2
-4	-3
-5	5

 

위 의 표처럼 -1 부터는 부호가 계속 반전되는 것을 볼 수 있다.

즉 n의 절대값이 짝수이면 음수

n의 절대값이 홀수이면 양수가 된고 나머지 수들은 우리가 알고 있는 피보나치 수와 동일하다.

N이 음수인지 양수인지 구분하지 않아도 f(n)의 절대값의 값은 같게 된다.

 

즉 2번째 출력값을 구할 때에는 절대값만 취해주고 기존의 피보나치 수 구하듯이 진행하면 된다.

 

다음은 전체 코드이다

def fibo(a) :
    x1, x2 = 0, 1
    if a == 1 :
        return 1
    n = abs(a) 
    for _ in range(n) :
        x1, x2 = x2 , (x1 + x2 )%1000000000
    return x1



N = int(input())
if N == 0 :
    print(0)
    print(0)
elif N > 0 :
    print(1)
    print(fibo(N))
else :
    if abs(N)%2 == 0 :
        print(-1)
    else :
        print(1)
    print(fibo(N))

본 문제를 풀때 시간초과 문제가 발생하였다. 

 

fibo 함수 부분에 

    for _ in range(n) :
        x1, x2 = x2 , (x1 + x2 )
    return x1%1000000000

이렇게 작성하였을 때에는 시간초과가 발생하였다.

 

왜 이러한 문제가 발생하였는지 생각해 보았다.

 

큰 수를 단순히 더하는 과정이 오랜 시간이 걸린다는 생각이 들었다.

(가령 컴퓨터가 가산하는 방식은 비트연산을 통해서 진행되는데 이 과정이 오래 거렸을 것이라 예상된다.)

그래서 큰수를 계산한 다음에 10^9로 나누는 것이 아니라

매번 계산을 할때마다 나누는 방식을 사용했다.

 

단순한 생각으로 문제를 해결하긴 했지만

이 문제에 대해서는 정확하게 공부 한 이후에 다시 포스팅 하도록 하겠습니다.

감사합니다.