[DP/동적계획법] 백준 1788 피보나치 수의 확장 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1788번: 피보나치 수의 확장

 

 

 

2. 문제 풀이

 피보나치의 '음수 부분'을 구하는 문제입니다. 본래, 피보나치는 n = 2부터 시작하죠.

 

n = 1일 때, f(1) = f(0) + f(-1) 이므로 f(-1) = f(1) - f(0) = 1

  피보나치의 정의를 역이용하면, f(-1)도 구할 수 있습니다. 즉, 음수 부분을 구할 때에는 조금 식이 달라집니다.

 

 

f(n-2) = f(n) - f(n-1)

f(-1) = f(1) - f(0) = 1
f(-2) = f(0) - f(-1) = -1
f(-3) = f(-1) - f(-2) = 2

  반대로 n은 1부터 시작해서 0, -1, -2로 낮아집니다.

 

 

 

3. 코드

# 입력
n = int(input())

# DP
# n이 양수일 때
if n > 0:
    cache = [0, 1]
    for i in range(2, n+1):
        cache.append((cache[i-1] + cache[i-2]) % 1000000000)
    print(1)  # 양수
    print(cache[n])

# n이 0일 때
elif n == 0:
    print(0)
    print(0)

 n이 양수일 때에는 기존의 피보나치 수열과 동일하게 풀이합니다.

 

 

# n이 음수일 때
# f(n-2) = f(n) - f(n-1)
else:
    cache = [1, 0]  # f(1), f(0)
    for i in range(-n):
        tmp = cache[i] - cache[i+1]
        if tmp < 0:
            tmp = -tmp % 1000000000
            cache.append(-tmp)
        else:
            cache.append(tmp % 1000000000)
    print(-1 if cache[-n+1] < 0 else 1)
    print(abs(cache[-n+1]))

 n이 음수일 때가 문제입니다. 리스트의 인덱스는 음수가 될 수 없으므로, 양수로 표현하되 cache[2]부터 f(-1)를 나타냅니다. 따라서 f(n)은 cache[-n+1]입니다.

 또 주의할 점은 음수의 나머지입니다. -2를 10으로 나눈 나머지는 '2'가 아니라 '8'입니다. 10씩 더해 양수로 만든 다음에 나머지를 구하기 때문에 (-2 + 10) % 10 = 8입니다. 문제에서는 절댓값의 나머지를 구해야 하므로, 음수이면 양수로 만든 다음에 나머지를 구해야 합니다.