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

💡문제접근

• 피보나치 수열을 구하는 과정에서 메모리 초과가 발생했다. 매우 큰 값을 저장하기 위해서 1,000,000,000으로 나눈 나머지의 값을 저장하는 코드로 바꿨더니 AC를 받았다.
• 규칙은 아래와 같다.
  ①. 양수인 경우 값을 1,000,000,000으로 나눈 나머지를 출력
  ②. 음수인데 이 음수의 절댓값이 짝수인 경우 음수가 됨
  ③. 음수인데 이 음수의 절댓값이 홀수인 경우 양수가 됨

💡코드(메모리 : 70508KB, 시간 : 320ms)

n = int(input())

dp = [0, 1, 1]
for i in range(3, abs(n)+1):
    dp.append((dp[i-2] + dp[i-1]) % 1000000000)

if n < 0 and abs(n) % 2 == 0:
    if -dp[abs(n)] < 0:
        print(-1)
        print(dp[abs(n)] % 1000000000)
    elif -dp[abs(n)] > 0:
        print(1)
        print(dp[abs(n)] % 1000000000)
    else:
        print(0)
        print(0)
elif n < 0 and abs(n) % 2 != 0:
    if dp[abs(n)] < 0:
        print(-1)
        print(dp[abs(n)] % 1000000000)
    elif dp[abs(n)] > 0:
        print(1)
        print(dp[abs(n)] % 1000000000)
    else:
        print(0)
        print(0)
elif n > 0:
    print(1)
    print(dp[n] % 1000000000)
else:
    print(0)
    print(0)

💡소요시간 : 7m