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

문제 풀이

이해가 잘 안 될 때 직접 그림을 그려보는 것도 좋은 방법이다.

1열 : N, 2열 : 0이 등장하는 횟수, 3열 : 1이 등장하는 횟수라고 보면 될 것 같다.

이렇게 쓰고보니 2열과 3열에서 규칙이 보여 아래와 같이 작성해봤다.

1의 개수처럼 0도 피보나치로 가능하였기 때문에

아래의 코드처럼 돌렸지만 시간 초과가 나왔다.

import sys


def fibonacci0(n):
    if n == 0:
        return 1
    elif n == 1:
        return 0
    else:
        return fibonacci0(n-1)+fibonacci0(n-2)


def fibonacci1(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci1(n-1)+fibonacci1(n-2)


T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    # r = 1 if N != 1 else 0
    print(fibonacci0(N), fibonacci1(N))

 

 

위의 코드는 반복문이 돌 때마다 해당 수까지의 계산을 다시 해줘야 되기 때문에 시간 초과가 날 것이라고 생각해서

 

배열을 이용하여 해당 위치에 대한 값을 반환시켜주면 시간초과가 나지 않을 것 같아 아래처럼 코드를 짰다.

zero = [1, 0, 1]
one = [0, 1, 1]

T = int(input())
for _ in range(T):
    N = int(input())
    if len(zero) <= N:
        for i in range(len(zero), N + 1):
            zero.append(zero[i - 1] + zero[i - 2])
            one.append(one[i - 1] + one[i - 2])
    print(f"{zero[N]}", f"{one[N]}")

첫 번째 코드에 비해 계산량이 훨씬 적어져서 시간 초과가 나지 않는다.

 

예를 들자면 테스트 케이스가 T=3, N=10000, N=5000, N=50000 이 들어왔을 경우

첫 번째 코드에서는 N=10000에 대한 계산이 끝나면 5000에 대한 계산, 50000에 대한 계산을 다시 해줘야 되기 때문에 시간이 많이 걸리게 되고 두 번째 코드에서는 처음 10000에 대해서 계산을 하고, 5000에 대한 값은 이미 배열에 들어있기 때문에 그냥 return을 시켜주고, 50000에 대한 값은 10001에 이어서 50000까지 계산을 해서 값을 반환시켜준다.

 

상당한 시간을 낭비하지 않기 때문에 시간초과가 나지 않는 것 같다.