[Python] 1788 - 피보나치 수의 확장 (실버3)

1. 문제 설명

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

1788번: 피보나치 수의 확장

 

---

2. 아이디어

헷갈린다면 직접 피보나치 수의 음수부를 써보면 이해가 갈 것이다.

패턴은 같은데 번갈아가며 음수값이 나옴을 확인할 수 있다.

n이 0보다 작으면서 짝수번째에는 무조건 -1을 출력하고 시작하면

나머지는 그냥 피보나치 수열 문제와 다를 것이 없다.

 

그리고 나는 아마 이때쯤에 모듈러 연산이라는 개념을 알게되었던 것 같다.

쉽지만 굉장히 중요한 개념이므로 이것도 따로 포스트를 다루도록 하겠다. 

 

---

3. 코드

cache = [0, 1, 1]

def solution():
    n = int(input())
    cache[1], cache[2] = 1, 1

    if n < 0 and n % 2 == 0:
        print(-1)
    elif n == 0:
        print("0\n0")
        return
    else:
        print(1)

    for idx in range(3, abs(n) + 1):
        cache.append((cache[idx - 2] + cache[idx - 1]) % 1000000000)
    print(cache[abs(n)])

solution()