[알고리즘/인프런] 계단 오르기

문제

---

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

 

풀이

---

/**
 * 다이나믹 프로그래밍(동적 계획법)
 * - 점화식(관계식)을 만드는 것이 중요
 * - 문제를 작은 단위로 쪼개서 구하고, 이걸 기록해뒀다가 문제 범위(데이터 범위) 넓히기
 * - dy[n] = dy[n-1] + 3처럼 관계를 구한다.
 * - 많은 문제를 풀어봐야 한다.
 */

function solution(n) {
  const dy = Array.from({ length: n + 1 }).fill(0);

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

  return dy[n];
}

console.log(solution(7));

이 문제의 도착지는 마지막 계단인 n이므로 정답은  dy[n]을 리턴한다. 

돌다리를 건너거나 어딘가를 거쳐서 목적지에 도착하는 문제인 경우, dy[n+1]을 해야 답을 구할 수 있다.