계단오르기

문제

제한사항

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

입출력 예

풀이

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));

• 동적계획법, 동적 프로그래밍, 다이나믹 프로그래밍
• 문제를 직관적으로 알 수 있는 크기로 줄여 범위를 넓혀나가며 답을 찾는다.
• 점화식을 알아내 답을 누적해나간다.
• bottom - up 방식
• 이문제에선 첫번째 계단을 올라가는 방식은 1개, 두번째 계단을 올라가는 방식은 3개이다.
• 이걸 토대로 3번째 계단에 올라는 방식은 1번째 계단에서 올라가는 방식, 2번째 계단에서 올라가는 방식 수를 더하면 나오게 된다.
• 점화식을 알았으니 반복문을 통해서 아래서부터 위로 답을 찾아나아가면 된다.