[JS] 코딩 테스트 문제 : 계단오르기 [동적계획]

문제 : 계단오르기

문제 설명

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

그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

▣ 입력설명

첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다.

▣ 출력설명

첫 번째 줄에 올라가는 방법의 수를 출력합니다.

### **▣ 입력예제 1** 7

▣ 출력예제 1

21

내코드

// BFS 활용 방식
// 아래 방식의 단점은  중복된 계산을 반복할 수 있습니다.
function solution(n) {
  let answer = 0;
  const steps = [1, 2];
  let que = [0]

  // que 가 모두 비워질 때 까지 반복
  while (que.length > 0) {
    // que 에 있는 마지막 계단 위치 추출
    let current = que.pop()

    // 계단 위치가 마지막 계단 위치라면 답을 1 증가시키고 아래 과정을 스킵
    if (current === n) {
      answer++
      continue;
    }

    // 계단에서 움직일 수 있는 경우의 수 만큼 que 에 추가
    for (const s of steps) {
      let tempStair = current + s
      if (tempStair <= n) que.push(tempStair)
    }
  }

  return answer;
}

console.log(solution(7)); // 21


// 동적계획 방식
// 1칸, 2칸, 4칸 씩 계단을 움직일 수 있다면 n 번째 계단에서 최종 목적지에 도착할 수 있는 총 경우의 수는 n+1,n+2,n+4 번째 계단의 이동할 수 있는 경우의 수의 합이므로
// 마지막 계단부터 계산하여 0 번째 계단 즉 처음부터 최종 목적지에 도착할 수 있는 총 경우의 수를 구하는 방식
// ex) 2번째 칸에서 최종 목적지에 도착할 수 있는 총 경우의 수는 1,2,4 씩 움직인 위치 즉 3,4,6 번째 계단에서 최종 목적지에 도착할 수 있는 경우의 수의 합이다.
function solution(n) {
  let answer;
  const steps = [1, 2, 4];
  let stairArr = Array(n + 1).fill(0)
  stairArr[n] = 1

  // n-1 번째 부터 -1 해가며 0 까지 반복
  for (let i = n - 1; i >= 0; i--) {
    // 움직일 수 있는 경우의 수 만큼 반복하며 현재 위치에서 이동하여
    // 도착할 수 있는 계단위치의 경우의 수를 모두 더하여 현재 위치에서 도착할 수 있는 모든경우의 수를 저장
    for (const s of steps) {
      if (i + s <= n) stairArr[i] = stairArr[i] + stairArr[i + s]
    }
  }

  // stairArr[0] 즉 계단에 오르기전 n 번째 계단에 도달하는 모든 경우의 수를 의미합니다.
  answer = stairArr[0]
  return answer
}

console.log(solution(7)); // 31

첫번째 BFS 방식 풀이

1. 움직일 수 있는 거리들을 배열로 steps 변수에 저장, 계단위치를 큐형태로 저장해 활용할 변수 que 선언 후 [0] 로 초기화
2. que 가 모두 비워질 때 까지 반복하는 while 문 안에서 que 에 있는 마지막 계단 위치 추출해 current 변수에 저장
3. 이동할 수 있는 경우의 수 만큼 반복하며 current 계단 위치에서 이동한 계단 위치들을 que 에 추가
4. 만약 이동하기전에 이미 계단 위치가 마지막 계단 위치라면 답을 1 증가시키고 이동 과정을 스킵
5. 최종적으로 이동할 수 있는 모든 경우의 수를 가진 anwer 를 반환

단점

중복된 계산을 반복할 수 있습니다.

예를 들어 1칸 이동 후 2칸 이동한 경우와 2칸 이동 후 1칸 이동한 경우는 결과적으로 3번째 계단에 도착했지만 다른 경우의 수로 도착했으므로 3번째 칸에서 이동하는 경우의 수를 중복으로 구하는 상황이 발생합니다.

두번째 동적계획법 방식 풀이

1. 움직일 수 있는 거리들을 배열로 steps 변수에 저장, 각 계단에서 마지막 계단까지 도착할 경우의 수들을 저장할 배열 변수 stairArr 를 마지막 계단 위치(n) 만큼 선언 후 모두 0으로 초기화
2. n-1 번째 부터 -1 해가며 0 까지 반복하는 중 이동할 수 있는 경우(steps) 만큼 반복하며 현재 위치에서 이동하여 도착할 수 있는 계단위치의 경우의수를 모두 더하여 현재 위치의 도착할 수 있는 모든경우의 수를 저장합니다.
3. stairArr[0] 즉 처음부터 마지막 계단에 도달하는 모든 경우의 수를 anwer 에 저장 후 반환

---

참고

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&unitId=64174