문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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가지 방법으로 멀리 뛸 수 있습니다.
문제풀이
💡 문제풀이 과정
- 주어진 매개변수
n에 1부터 순서대로 대입해보면 규칙이 보이는 문제였다.피보나치 수열을 구하는 문제로, 일전에 피보나치 수 문제를 먼저 풀었던 것 처럼, 아래와 같이 정리할 수 있겠다. (n이 3이상이면, 피보나치 수의 규칙을 따른다)# 멀리 뛰기 경우의 수 n = 1 = 1개 = [1] n = 2 = 2개 = [1,1], [2] n = 3 = 3개 = [1,1,1], [1,2], [2,1] n = 4 = 5개 = [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2] n = 5 = 8개 = [1,1,1,1,1], [1,1,1,2], [1,1,2,1], [1,2,1,1], [2,1,1,1] , [2,2,1], [1,2,2], [2,1,2] # 규칙: 피보나치 수열 F(1) = 1 F(2) = 2 n이 3이상이면, 피보나치 수의 규칙을 따른다. F(n) = F(n-1) + F(n-2) F(3) = F(1) + F(2) = 1 + 2 = 3 F(4) = F(2) + F(3) = 2 + 3 = 5 F(5) = F(3) + F(4) = 3 + 5 = 8 a1 + b1 = result1 a2(=b1) + b2(=c1) = result2(=a2+b2) a3(=b2) + b3(=c2) = result3(=a3+b3)
✅ 답안 #1
function solution(n) {
let a = 0, b = 1, result = 0;
for (let i = 2; i <= n + 1; i++) {
result = (a + b) % 1234567;
a = b;
b = result;
}
return result;
}✅ 답안 #2
function solution(n) {
let answer = 0;
let fibo = [0, 1, 2];
for (let i = 3; i <= n; i++) {
fibo[i] = (fibo[i-1] + fibo[i-2]) % 1234567;
}
answer = fibo[n];
return answer % 1234567;
}