[JS] 프로그래머스 코딩테스트 연습 | L2 멀리 뛰기

1. 문제 설명

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

2. 제한 사항

n은 1 이상, 2000 이하인 정수입니다.

3. 입출력 예

n result
4 5
3 3

입출력 예 #1

위에서 설명한 내용과 같습니다.

입출력 예 #2

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

문제풀이

이번 문제는 몰라서 결국 다른 사람 답을 참조해 풀었다
풀기 위해선 문제의 규칙을 찾아야 하는데

s = 1 --> 1
s = 2 --> 2
s = 3 --> 3
s = 4 --> 5
s = 5 --> 8
s = 6 --> 13

f(n) = f(n-1) + f(n-2)

즉 피보나치 수열과 같은걸 알 수 있다

function solution(s) {
  // s가 1이나 2일 땐 그냥 리턴
  if (s === 1) return 1; 
  if (s === 2) return 2;

  let answer = 0;
  let n1 = 0,
    n2 = 1;
  for (let i = 2; i <= s + 1; i++) {
    answer = n1 + (n2 % 1234567);
    n1 = n2; // n1이 기존 n2가 되고
    n2 = answer; // n2는 n1 + n2 % 1234567이 된다
  }
  return answer % 1234567;
}

% 1234567의 이유
: 피보나치 수열이 진행되다 보면 수가 겁나 커져서 표현할 수 없게 됨 그걸 방지하기 위해 1234567로 나눈 나머지 사용하는 것

다른 사람 풀이

재귀를 사용해 푼 풀이

function solution(num) {
  if (num === 1) return 1;
  if (num === 2) return 2;
  return solution(num - 1) + solution(num - 2);
}

딱 피보나치 정석으로 푼 풀이 방식이다

example
num = 4
→ sol(3) + sol(2)
→ sol(2) + sol(1) + 2
→ 2 + 1 + 2

---

아 머리가 딸리는건지 재귀적 방식은 생각하기 어렵다. 재귀랑 피보나치 수열 관련 문제를 좀 더 풀어봐야겠다 ㅠ