[프로그래머스] 멀리 뛰기 javascript

문제 설명

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

n	result
4	5
3	3

입출력 예 설명

입출력 예 #1
위에서 설명한 내용과 같습니다.

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

 

✍️ 나의 풀이방식 (🚨 콜스택 오버플로우)

function solution(n) {
    let arr = [0, 1, 2];
    for(let i = 3; i <= n; i++) {
        arr.push(arr[i - 1] + arr[i - 2]);
    }
    return arr[n] % 1234567;
}

이 문제는 피보나치 수열과 비슷한데, 

1칸을 갈 때 뛰는 방법은 1가지, 2칸을 갈 때 뛰는 방법은 2가지가 존재한다. 

3칸을 갈 때는 (2칸에서 + 1칸 뛰기) + (1칸에서 + 2칸 뛰기)의 방법을 적용하면,

1칸 갈 때 뛰는 방법의 경우의 수 + 2칸 갈 때 뛰는 방법의 경우의 수 = 3칸을 가는 경우의 수가 된다.

그러나 위처럼 재귀를 사용했을 때 너무 많은 호출이 이뤄질 경우, 콜스택 오버플로우가 발생한다.

 

✍️ 다른 사람의 풀이방식

1. BigInt를 써서 풀기 

function solution(n) {
    let arr = [0n, 1n, 2n];
    for(let i = 3; i <= n; i++) {
        arr.push(arr[i - 1] + arr[i - 2]);
    }
    return arr[n] % 1234567n;
}

BigInt는 Number 원시 값이 안정적으로 나타낼 수 있는 최대 값인 2^53 - 1 보다 큰 정수를 표현할 수 있는 내장 객체다.

정수 리터럴 뒤에 n을 붙이거나 BigInt()를 호출해 생성할 수 있다.

 

 

2. forEach를 사용해서 연산하기

function solution(n) {
  if (n < 2) return 1;
  const count = [0, 1, 2, ...Array(n - 2).fill(0)];
  count.forEach((_, i) => {
    if (i > 2) count[i] = (count[i - 2] + count[i - 1]) % 1234567;
  });
  return count[n];
}

 

 

참고자료

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/BigInt