안녕하세요 오랜만입니다.
코테-피보나치
오늘은 이 문제와 싸웠습니다.
뭔가 규칙이 있을법한데 ... 싶어서 세보니 피보나치 규칙이였습니다. 다른분들도 피보나치 수열로 푸셨더라구요 하지만 뭔가 이상했습니다 지금까지의 코딩테스트의 문제는 직관적인 규칙들이 존재해 로직을 작성했는데 이 문제는 뭔가 피보나치 수열을 사용해야 한다는 것을 직관적으로 파악 할 수 없었습니다. 그런데!!!!
다른분의 풀이에서 알게 된 사실은 이문제는 N칸까지 가는 경우의 수는 N-1 칸에서 1칸 뛴 경우의 수와 N-2에서 2칸 뛴 경우의 수의 합이라는 공식을 알게 되었습니다!!
즉 N칸인 경우의 수=N-1칸의 경우의수 + N-2칸의 경우의 수 로 정확하게 피보나치 수열과 일치해 궁금증을 해결 할 수 있었습니다!!!