[Python] 백준 1788: 피보나치 수의 확장

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

1788번: 피보나치 수의 확장

1차 시도(Fail) - 메모이제이션

N = int(input())

lst = [0] * (abs(N)+2) #절댓값만큼의 리스트 만들어주기
if N > 0:
    lst[1] = 1
    for i in range(2,N+1):
        lst[i] = lst[i-1] + lst[i-2]
    print(1)
    print(lst[N])
elif N < 0:
    lst[-1] = 1
    for i in range(abs(N)-1,-1,-1):
        lst[i] = lst[i+2] - lst[i+1]
    if lst[0] > 0:
        ans= 1
    elif lst[0] == 0:
        ans = 0
    else:
        ans = -1
    print(ans)
    print(abs(lst[0]))
else:
    print(0)
    print(0)

 

메모이제이션 방법으로 풀어봤는데 append도 안 쓰고 그래서 깔끔하게 나올 줄 알았다... DP 문제를 풀다보니 이제 메모리 초과가 적지 않게 뜨는데 늘 왜 뜨지? 싶어진다 나 너무 리스트 길게 만들어...

 

2차 시도(성공) - DP

메모리 초과가 뜨는 이유는 리스트를 너무 길게 만들어서! 리스트를 딱 필요한 만큼만(길이 2만큼만) 만들고 while문을 돌면서 피보나치 수를 구해주려 했다. 시간은 너무 많이 걸렸고 메모리도 난리지만 어쨌든 통과! 통과 후 시간을 더 줄이려고 노력했다.

fib = [0,1]
N = int(input())
if abs(N) > 1:
    cnt = 0
    if N >1:
        while cnt !=N:
            tmp1 = fib[1]
            tmp2 =  fib[1] + fib[0]
            fib[0] = tmp1
            fib[1] = tmp2
            cnt += 1
        print(1)
    else:
        while cnt != abs(N):
            tmp1 = fib[1] - fib[0]
            tmp2 = fib[0]
            fib[0] = tmp1
            fib[1] = tmp2
            cnt += 1
        if fib[0] > 0:
            print(1)
        else:
            print(-1)
    print(abs(fib[0])%1000000000)
else:
    print(abs(N))
    print(abs(N))

 

최종 - DP

N = int(input())
fib = [0, 1]
for i in range(2, abs(N) + 1):
    fib.append((fib[i - 1] + fib[i - 2]) % 1000000000)
if N % 2 == 0 and N < 0:
    print(-1)
elif N == 0:
    print(0)
else:
    print(1)
print(fib[abs(N)])

DP의 정석대로 규칙을 찾아내서 if문 최대한 덜 돌게 해서 클리어! 깔끔해!