10-1. 계단 오르기 (동적 계획법)

동적 계획법(dynamic programming, DP)이란?

특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

 

문제를 보며 예시를 들어 보겠습니다.

 

문제

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

 

 

 

먼저 1번 계단을 오르는 방법의 수는 1가지입니다.

그리고 2번째 계단을 오르는 방법의 수는 2가지이고요

 

그렇다면 3번째는 어떨까요?

3번째에 다다르는 방법은 1번째에서 오던가 혹은 2번째 계단에서 오던가 2가지입니다.

그런데 1번째 계단을 이르는 방법의 가지 수는 1개이고 2번째는 2개입니다.

 

따라서 1번째 계단을 이르는 방법 + 2번째 계단을 이르는 방법 = 3번째 계단을 이르는 방법의 가짓수

 

라고 할 수 있습니다.

마찬가지로 4번째 , 5번째... n번째도 마찬가지입니다.

 

공식으로 보자면

 

dy [n] = dy [n-2] + dy [n-1]이라고 할 수 있습니다.

 

그리고 동적 계획법으로 문제를 풀 때에는 이러한 계산했던 결과를 기록할 배열을 이용해 문제를 풀어야 합니다.

 

이제 코드로 문제를 풀어보면 되겠습니다. 

풀이

 

function solution(n) {
  let answer = 0;
  let dy = Array.from({ length: n + 1 }, () => 0);
  dy[1] = 1;
  dy[2] = 2;
  for (let i = 3; i <= n; i++) {
    dy[i] = dy[i - 2] + dy[i - 1];
  }
  answer = dy[n];
  return answer;
}

console.log(solution(7));