반응형

LeetCode 문제 해석 및 풀이 방법
문제 70. Climbing Stairs(계단 오르기)
난이도 : 쉬움🟢 바로가기
문제 설명
영문
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
한글
당신은 계단을 오르고 있습니다. 꼭대기에 도달하려면 n단계가 필요합니다.
매번 1단계 또는 2단계를 오를 수 있습니다. 정상까지 올라갈 수 있는 방법은 몇 가지입니까?
제한조건
- 1 <= n <= 45
입출력 예
입력 | 출력 |
n = 2 | 2 |
n = 3 | 3 |
해답 및 해설
파이썬 (Python)
class Solution: def climbStairs(self, n: int) -> int: if n == 1: return 1 elif n == 2: return 2 n -= 2 a, b = 1, 2 while n: a, b = b, a+b n -= 1 return b
피보나치로 풀면 되는 유명한 문제. n번째 계단을 오르는 방법은 n-1번째 계단을 오르는 방법들에서 계단 한 칸을 오르는 것과 n-2번째 계단을 오르는 방법들에서 계단 2칸을 오르는 방법이 있다. 따라서 계단을 오르는 방법의 가짓수는 다음 항이 이전 두 항을 더한 값이 되는 수열, 즉 피보나치 수열이 되게 된다.
class Solution: def climbStairs(self, n: int) -> int: dp = [-1]*(n+1) dp[0], dp[1] = 1, 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]
굳이 이렇게 풀 이유는 없지만 neetcode 로드맵에서 나온 대로 dp로 풀면 다음과 같다. 보통 재귀로 풀 때와 dp로 풀 때를 비교해주는 편
반응형
'🖥️ 문제 풀이 > 리트코드(Leetcode)' 카테고리의 다른 글
[LeetCode 해석 및 풀이] 198. House Robber(집도둑) (0) | 2024.09.17 |
---|---|
[LeetCode 해석 및 풀이] 746. Min Cost Climbing Stairs(최소 비용 계단 오르기) (0) | 2024.09.17 |
[LeetCode 해석 및 풀이] 17. Letter Combinations of a Phone Number(전화번호의 문자 조합) (0) | 2024.09.17 |
[LeetCode 해석 및 풀이] 131. Palindrome Partitioning(회문 분할) (0) | 2024.09.16 |
[LeetCode 해석 및 풀이] 79. Word Search(단어 검색) (0) | 2024.08.19 |
댓글