gumaguma11211   1년 전

문제 풀면서 쓴거라 조금 난해하긴 합니다

피보나치 수열 P에 대해 P[a] 를 p, P[b]를 q라 하면

1 p 1 0

2 q 0 1

3 p q 1 1

4 p qq 1 2

5 pp qqq 2 3

6 ppp qqqqq 3 5

7 ppppp qqqqqqqq 5 8

8 8 13 8 13

9 13 13 21

P

1 2 3 4 5 6 7 8 9 10

1 1 2 3 5 8 13 21

S(a, b) = P[a] *(1 + S(1, b -a - 1)) + P[a+1] * S(1, b - a)

처음에 여기까지만 유도하고 문제를 풀었는데, 메모리 초과가 뜨더군요

그래서 S를 사용하지 않는 방법이 있을까 하고 a가 1인 특수한 케이스에 대해 생각해봤습니다

S(1, b) = P[1] * (1 + S(1, b - 2)) + P[2] * S(1, b - 1)

S(1, b) = 1 + S(1, b - 2) + S(1, b - 1)

S(1, b) = 1 + S(1, b) - P[b-1] - P[b] + S(1, b) - P[b]

S(1, b) = 1 + 2*S(1, b) - P[b] - P[b] - P[b-1]

S(1, b) = P[b] + P[b] + P[b - 1] - 1

S(1, b) = P[b] + P[b + 1] -1

S(1, b) = P[b + 2] - 1

b가 2일때, 엣지케이스 검사:

S(1, 2) == P[4] - 1

=> 모든 b 값에 대하여 성립

이렇게 되면 S를 사용하지 않고 P만 사용할 수 있죠

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