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

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

프로그래머스

---

1) 풀이

거의 며칠동안 풀던 문제.. 계속 재귀함수로 풀어보고, 재귀함수가 너무 오래 걸리나? 해서 While문으로도 풀어보고 하다가 도저히 안 돼서 찾아보니 다이나믹 프로그래밍(동적 프로그래밍) 의 점화식을 이용해서 풀면 되는 문제였다.

 

동적 프로그래밍을 이용하여 점화식을 세운 다음, 메모이제이션 기법을 사용하면 간단하게 풀렸다

메모이제이션 기법이란, 이전에 계산한 값을 저장해놓고 그 값이 필요할 때마다 계산을 다시 해주는 것이 아니라 그 저장된 값을 불러와서 사용하는 것이다. 재귀로 푸는 대표적인 문제인 피보나치를 예시로 들면 f(5)의 값을 구하기 위해서는 그 앞의 f(3) f(2) 등이 계속해서 반복적으로 계산되는데 이때 메모이제이션 기법을 활용하면 한 번만 계산한 뒤 그 값을 저장해놓고 필요할 때마다 꺼내서 활용하면 되기 때문에 따로 계산을 해주지 않아도 된다.

 

그러면 해당 문제의 점화식은 어떻게 세워볼 수 있을까?

예시를 보면 다음과 같다n이 3일때 3, n이 4일때 5

 

n을 더 줄여봤을 때는 어떻게 될까문제에서 한번에 1칸 혹은 2칸밖에 뛰지 못한다고 했으므로n이 2일때는 (1,1) (2) 의 두가지 경우 즉n이 2일때 2n이 1일때는 (1) 의 한가지 경우 즉n이 1일때 1

 

아까 전 문제의 예시와 함께 줄 세워보면 다음과 같다

n	방법의 개수
1	1
2	2
3	3(2+1)
4	5(3+2)

이렇게 줄 세워보니 규칙성이 좀 보인다!

앞서 말했던 피보나치 수열처럼, f(n)=f(n-1)+f(n-2) 인 것!

 

저 점화식은 n이 3일때부터 시작하므로, 각 인덱스가 n이 되도록 f(0)의 경우에도 0을 넣어주고 f(1)=1, f(2)=2 를 넣어준 뒤 n이 3일때붙 해당 방법으로 답을 계산하면 된다! 

%1234567 의 경우에 저번에 배웠던 (A+B)%C=((A%C)+(B%C))%C 를 활용했다 

그렇게 풀어주면 정답,, 재귀나 같은 값을 활용하는 경우가 정말 많은데 이때 메모이제이션 기법을 이용하면 정말 좋은듯!

꼭 기억해놓자,,

2) 최종 소스코드

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

3) 참고자료

https://blog.naver.com/PostView.nhn?blogId=dgsw102&logNo=221224601208 

제3강. 점화식 심화, 동적 프로그래밍(DP)