twomidxerath   1년 전

a 번째 항이 t, a + 1 번째 항이 k라고 치면

t, k, t+k, t+2k, 2t+3k, 3t + 5k, 5t + 8k... 의 규칙을 가집니다. 여기서 나오는 각각의 숫자들이 피보나치 수열 안에 존재하는 수이고, 피보나치 수열의 특성상 이후로 붙는 t와 k의 계수 또한 피보나치수열에 포함되겠죠


그렇다면 n번째 항을 fibo(n)이라고 하면

fibo(n) = fibo(k)*fibo(n-k+1) + fibo(k-1)*fibo(n-k) 가 되는 것 같습니다... 이러한 방식으로 분할 정복을 사용할 수 있을 것 같은데, 제가 혼자 계산해본 식이 맞나요?

not_strober   1년 전

T(n) = T(k) + T(n-k) + O(1). k가 n/2일 때 T(n) = 2T(n/2) + O(1). 따라서 해당 풀이법의 시간 복잡도는 O(n)으로, 불가능입니다.

zenith82114   1년 전

구현해서 제출해 보니 잘 작동합니다. 시간은 O(log N)일 것으로 생각됩니다. https://www.acmicpc.net/source/96750903

not_strober   1년 전

제가 분할 정복에서 memoization을 고려하지 않았네요. O(log N)이 맞네요.

댓글을 작성하려면 로그인해야 합니다.