[프로그래머스_자바스크립트] Lv.2 멀리 뛰기 / 동적 계획법 (Dynamic Programming)

 

[Javascript_ 멀리뛰기]

 

프로그래머스

 

 

---

 

<STUDY>

 

📢 문제 📢

 

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

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

 

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

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

 

제한 사항

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

 

❗ 아이디어

 

- 1번째 전 값에 2번째 전 값을 더하면 현재 값이 나온다.

 

---

 

<전체 코드>

 

# 처음 풀이

function solution(n) {
  let answer = 1;
  let before = 1;

  for (let i = 1; i < n; i++) {
    answer += before;
    before = answer - before;
    answer = answer % 1234567;
  }
  answer = answer % 1234567;
  return answer;
}

 

# 동적 계획법

function solution(n) {
  let dp = [];
  dp[0] = 1;
  dp[1] = 2;

  for (let i = 2; i < n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2] % 1234567;
  }

  return dp[n - 1] % 1234567;
}

 

---

 

규칙성을 조금만 생각해 보면 바로 동적 계획법을 사용하는 것을 알 수 있는데

처음에 그 생각을 못하고 아래 코드와 같이 동일한 계산을 반복했다.

 

for (let i = 1; i < n; i++) {
    answer += before;
    before = answer - before;
    answer = answer % 1234567;
}

 

알고리즘을 바로 생각할 수 있도록 더 노력해야겠다..ㅠㅠ

 

---

 

🔆프로그래머스 Lv2. 멀리 뛰기🔆

 

👉ez1n github 구경하기👈

 

ez1n - Overview