풀이 과정
이동할 칸이 1칸인 경우 경우의 수는 1
이동할 칸이 2칸인 경우 경우의 수는 2
이동할 칸이 3칸인 경우 경우의 수는 앞서 본 두 경우의 수의 합
👉 각 칸으로 이동하는 경우의 수는 피보나치 수열과 같음
(1), 1, 2, 3, 5, 8, 13, ...
코드
function solution(n) {
const arr = [1, 1];
for (let i = 2; i <= n; ++i) {
arr.push((arr.at(i - 2) + arr.at(i - 1)) % 1234567);
}
return arr[n];
}🤔
처음에 순열만 생각해서 오랜만에 순열 공식 보고 팩토리얼 함수 만들고 어쩌고 풀었는데 케이스 3번부터 다 통과가 안 됐다. 질문하기를 봐도 정확한 원인을 모르겠다. 오버플로우 문제인 것 같긴 한데 매번 1234567로 나눠줬는데 흠... 결국 이게 피보나치 수열이라는 힌트를 얻고 풀 수 있었다.
방황하다가 1시간이나 걸린 문제 🫠
