[2023-02-23]

Start

FibFrog에서 다시 시작..

---

FibFrog 문제

정답 코드

 

1. array A의 크기가 100,000이라는 것을 알고 피보나치 수열을 27개만 구함. 0부터 26까지 구했고 26번째 피보나치 수가 아마 123,000쯤..? 되었던 것 같다.

2. 큐를 쓰든가 해서 시간복잡도를 줄여야하고

array A를 for문으로 반복하며 이전 출발 index와 가려고 하는 index의 차이가 피보나치 수만큼인지를 파악하는 방법보다는

 

1번에서 구해놓은 피보나치 수 배열을 for문으로 돌려서 이전 출발 index에서 피보나치 수를 더한 수가 array A에서 1인지를 파악하는 방법으로 접근해야한다.

 

이렇게 하면 시간복잡도의 늪에서 벗어날 수 있다.

 

아래는 FibFrog를 풀기 위한..생각의 늪이었다..

이렇게 생각하다가 문득 구해놓게 되는 피보나치 수열은 27개뿐이니까 피보를 돌리면..? 훨씬 시간복잡도가 줄지 않을까하는 생각을 하게 되었다..

큐를 사용하는 부분 빼고는 내가 생각한 방법대로 진행해서..나름 뿌듯하다..