[ 자바스크립트(JavaScript) ] section10 - 2 - 돌다리 건너기

📍 section10 - 2 - 돌다리 건너기

문제: 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철수는 돌다리를 건널 때 한 번에 한 칸 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요??

 

이전에 풀었던 계단 오르기 문제와 매우 흡사하다. 하지만 잘 생각해보면, dp[n]을 구하는 것이 아니라 dp[n+1]을 구하는 문제이다. 왜냐하면 개울을 건너기 위해서는 마지막 돌에 서있으면 안되고(dp[n]), 마지막 돌에서 한 칸 앞으로 전진해야 하기 때문(dp[n+1])이다.

 

728x90

 

let n = 7;

console.log(solution(n));

function solution(n){
  let dp = Array.from({length: n+2}, () => 0);

  dp[1] = 1;
  dp[2] = 2;

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

  return dp[n+1];
}