백준 1788 : 피보나치 수의 확장 (Python)

본문 링크

N=int(input())

# F(-1)=F(1)-F(0)
# F(-N) =F(-N+2)-F(-N+1)

if N==0:
    print(0,0,sep='\n')
    exit(0)
dp=[0]*( abs(N)+1)
dp[1]=1
if N<0:
    for i in range(2, abs(N)+1):
        dp[i]=(dp[i-2]-dp[i-1])
        if dp[i]<0:
            dp[i]%=-1000000000
        else:
            dp[i]%=1000000000
elif N>0:
    for i in range(2,N+1):
        dp[i]=(dp[i-1]%1000000000+dp[i-2]%1000000000)

if N<0:
    if dp[-N]<0:
        print(-1)
        print(abs(dp[-N]%-1000000000))
    else:
        print(1)
        print(dp[-N]%1000000000)
elif N>0:
    print(1)
    print(dp[N]%1000000000)

📌 어떻게 접근할 것인가?

피보나치 수에 새로운 규칙을 적용한 문제이다.
바로 $F(n)$ 이라는 피보나치 값이 있을때 $n$ 이 음수일때도 구하는 문제이다.
F(1)=F(0)+F(-1) 이고 이는 F(-1)=F(1)-F(0) 로 나타낼수있다.
이것을 점화식으로 바꾸면 F(-N) =F(-N+2)-F(-N+1) 이다.

따라서 $N$ 이 음수일때는 위 식을 적용시키고 $N$ 이 양수일때는 그대로 피보나치 수를 구해주면 된다.

✅ 코드에서 주의해야할 부분

• 리스트 값이 음수일때는 (-)1000000000 로 나머지값을 구해준다. 양수로 나머지 값을 구해주면 다른값이 나온다.
• $N$ 이 음수일때는 $DP[N]$ 이 아니라 $DP[-N]$ 리스트 값을 출력해준다.