숫자 n이 주어졌을 때, 첫 n개의 피보나치 수열 항의 합을 구하는 프로그램을 만들어 보겠습니다. 만약 계산 결과가 너무 커진다면 결과를 10^8 + 7로 나눈 나머지를 반환하도록 처리합니다.
문제 이해하기
예를 들어 입력이 n = 8이라면, 첫 8개의 피보나치 항은 0, 1, 1, 2, 3, 5, 8, 13이며 이들의 합은 다음과 같습니다.
0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33
따라서 출력 결과는 33이 됩니다.
해결 접근 방법
이 문제는 재귀 함수와 메모이제이션(memoization) 기법을 활용하면 효율적으로 해결할 수 있습니다. 풀이 과정은 다음과 같습니다.
- m := 10^8 + 7 (결과가 클 때 사용할 모듈로 값)
- memo := 새로운 딕셔너리(맵) 생성
- solve() 함수를 정의하며, 이 함수는 n과 m을 매개변수로 받습니다.
- n이 memo에 이미 존재하면 memo[n]을 그대로 반환합니다.
- n < 2이면 memo[n] := n으로 설정하고, 그렇지 않으면 memo[n] := (solve(n-1, m) + solve(n-2, m)) mod m으로 설정합니다.
- memo[n]을 반환합니다.
- 메인 부분에서 memo에 저장된 값들을 가져와 모두 더합니다.
구현 예제
아래 파이썬 구현 예제를 통해 더 자세히 살펴보겠습니다.
m = 10**8+7
memo = {}
def solve(n, m):
if n in memo:
return memo[n]
memo[n] = n if n < 2 else (solve(n-1, m)+solve(n-2, m)) % m
return memo[n]
n = 8
solve(n, m)
print(sum(list(memo.values())[:n]))입력
8
출력
33
동작 원리
solve() 함수는 재귀적으로 호출되며, 한 번 계산한 값을 memo 딕셔너리에 저장해 둡니다. 덕분에 동일한 피보나치 수를 반복해서 계산할 필요가 없어 시간 복잡도가 지수급인 O(2^n)에서 선형인 O(n)으로 크게 줄어듭니다. solve(n, m)을 한 번 호출하면 memo에는 F(0)부터 F(n)까지 모든 피보나치 수가 저장되며, 이 값들을 모두 더하면 첫 n개 항의 합을 손쉽게 얻을 수 있습니다.