1.5

문제 멀리뛰기

문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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 조합해서 규칙을 찾으려고 하다 보니 1,2,3,5.....
거꾸로봐도 피보나치..

과정1) 반복문으로 접근 => 절반만 통과

function solution(n) {
      let obj = {}
   for (i = 1; i <= n ; i++ ) {
        if(i <= 2) {
           obj[i] = i  
        }  else {
            obj[i] = obj[i-2] + obj[i-1]
        }
    }
    return  obj[n] % 1234567
}

과정2) 재귀로 접근 => 절반만 통과

function solution(n) {
     const jump = (num) => {
       if(num <= 2) {
           return num
        } 
      else {
           return jump(num - 1) + jump(num - 2) 
       }
    }
 return jump(n) % 1234567
}

과정3이자 정답)

function solution(n) {
    let obj = {}
    for (i = 1; i <= n ; i++ ) {
        if(i <= 2) {
           obj[i] = i  
        }  else {
            obj[i] = (obj[i-2] + obj[i-1] ) % 1234567
        }
    }
    return  obj[n] % 1234567
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

옛날옛날 큰 숫자를 이런 식으로 처리했던 문제를 봤던 기억이 나서 해봤는데 됐다...
이제는 공부하자........dynamic programming