[프로그래머스] Lv.2 멀리 뛰기 JavaScript

Janet·2023년 3월 27일
0

Algorithm

목록 보기
88/314

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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 이하인 정수입니다.

입출력 예

nresult
45
33

입출력 예 설명

입출력 예 #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;
}
profile
😸

0개의 댓글