[2023-02-28]

Start

---

Ladder 문제

정답 코드

Queue에 0부터 넣고 1, 2를 더해가며 가짓수를 찾는 방법을 생각해냈다.

결과는 시간초과

왜 이 문제가 피보나치에 있는 건지에 대해 고민했는데, 사다리를 오르는 방법이 F[n] = F[n - 1] + F[n - 2]를 따르고 있었다.

 

아래와 같이 피보나치 방법을 적용해서 문제를 풀었다.

똑같은 결과처럼 보이지만.. 아예 똑같은 결과는 아니다.

시간 안에 문제는 풀렸지만 답이 틀린 경우이다. got 0으로 나온 것들이 있는 것을 보면 구해야하는 피보나치 수보다 적게 구한 것 같다.

 

그.. modulo 법칙 중에 이런 것이 있다.

위의 법칙을 적용해서 문제를 다시 풀어보았다.

정확도는 100%로 맞았지만 timeout이 발생했다.

 

피보나치 수열을 만드는 횟수를 줄일 수 있도록 B[i]가 같은 값끼리 모아서 연산할 수 있도록 구성하였다.