📕 문제
문제설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.
제한조건
- n은 1 이상, 2000 이하인 정수입니다.
입출력 예
| n | result |
|---|---|
| 4 | 5 |
| 3 | 3 |
입출력 예 설명
입출력 예 #1
위에서 설명한 내용과 같습니다.
입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.
🤔 고민과정
- 피보나치 수를 이용해서 푸는 문제라고 한다. 이런 유형을 기억해 두었다가 다음에 사용하자.
▶ 뛸 수 있는 경우의 수가 피보나치 수처럼 늘어나는 것을 알 수 있다.
- 1칸을 뛰어야 할 때 : 1가지 [(1칸)]
- 2칸을 뛰어야 할 때 : 2가지 [(1칸, 1칸), (2칸)]
- 3칸을 뛰어야 할 때 : 3가지 [(1칸, 1칸, 1칸), (1칸, 2칸), (2칸, 1칸)]
- 4칸을 뛰어야 할 때 : 5가지 [(1칸, 1칸, 1칸, 1칸), (1칸, 2칸, 1칸), (1칸, 1칸, 2칸), (2칸, 1칸, 1칸), (2칸, 2칸)]
✅ 결과물
function solution(n) {
// 피보나치 수는 0번째 항은 0, 1번째 항은 1이지만
// 여기서는 0번째 항, 1번째 항 모두 1을 대입
let fibonacci = [1, 1];
// 2번째 항부터 계산하여 배열에 추가
for (let i = 2; i <= n; i++) {
fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % 1234567;
}
// n칸일 때 가지 수
return fibonacci[n];
}