멀리 뛰기

Problem. 멀리 뛰기

---

Link.

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

---

Description.

효진이는 멀리 뛰기를 연습하고 있습니다.

효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다.

칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 

멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 

여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 

 

※ 제한사항

• n은 1 이상, 2000 이하인 정수

입출력 예시

---

Approach. 

1) Dynamic Programming (DP)

• 추후에 설명 추가할 예정입니다
• 규칙을 찾자!
  • n = 1인 경우 / (1) / result: 1
  • n = 2인 경우 / (1, 1), (2) / result: 2
  • n = 3인 경우 / (1, 1, 1), (1, 2), (2, 1) / result: 3
  • n = 4인 경우 / (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2) / result: 5
  • n = 5인 경우 / (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1), (1, 2, 2), (2, 1, 2), (2, 2, 1) / result: 8
• 위의 경우의 수를 살펴보면 다음과 같은 규칙(점화식)을 찾을 수 있다:

An+2 = An+1 + An

• 이제 위의 점화식을 코드로 구현하면 끝!

---

My Answer. 

function solution(n) {
    // n = 1 => 1
    // n = 2 => 2
    // n = 3 => 3
    // n = 4 => 5
    // n = 5 => 8
    
    let dp = [];
    dp[0] = 1;
    dp[1] = 2;
    
    for(let i = 2; i < n; i++) {
        dp[i] = (dp[i-2] + dp[i-1]) % 1234567;
    }
    
    return dp[n-1];
}

---

References.

프로그래머스 - 멀리 뛰기 - 질문목록:

https://school.programmers.co.kr/questions/20546

프로그래머스

---

For Developer. 

• 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)