← 19주차 · DP 입문 (1차원)
쉬움DP

계단 오르기

n개의 계단을 올라요. 한 번에 1칸 또는 2칸을 오를 수 있을 때, 꼭대기에 도달하는 서로 다른 방법의 수를 반환해요.

결과가 커질 수 있으니 반복문으로 계산해요. 단순 재귀는 시간 초과가 나요.

예시

예시 1
입력
n = 2
출력
2
설명
1+1, 2 두 가지예요.
예시 2
입력
n = 3
출력
3
설명
1+1+1, 1+2, 2+1 세 가지예요.

제한 사항

  • 1 ≤ n ≤ 45
n번째 계단에 도달하는 방법은 (n-1)번째에서 1칸 오르거나 (n-2)번째에서 2칸 오르는 경우뿐이에요. 즉 f(n) = f(n-1) + f(n-2) 인 피보나치예요.
javascript
function climbStairs(n) {
  let a = 1;
  let b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}
이전 문제스트림 중앙값
다음 문제도둑질
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.