2086번 - 피보나치 수의 합
문제 풀면서 쓴거라 조금 난해하긴 합니다
피보나치 수열 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만 사용할 수 있죠
댓글을 작성하려면 로그인해야 합니다.
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만 사용할 수 있죠