📕문제
문제 설명
한 번에 1칸 또는 2칸을 오를 수 있을 때 n칸의 계단을 오르는 경우의 수가 몇개인지 구하는 문제다.
Example 1
n = 3 일 때
- 1 + 1 + 1
- 2 + 1
- 1 + 2
계단을 오를 수 있는 경우의 수는 3가지다.
📝풀이
직접 몇개의 계단에 대해 경우의 수를 구하다 보면 다음과 같은 규칙이 존재한다는 것을 쉽게 알아차릴 수 있을 것이다.
n개의 계단을 오르는 방법은n-1번째 계단을 오르고 한 칸 오르는 방법과 n-2번째 계단을 오르고 두 칸 오르는 방법이 있다.
즉 n칸의 계단을 오르는 경우의 수는 n-1칸의 계단을 오르는 경우의 수와 n-2칸의 계단을 오르는 경우의 수를 더한 것이 된다.
class Solution:
def climbStairs(self, n: int) -> int:
first, second = 1, 1
curr = 1
for i in range(n-1):
curr = first + second
first = second
second = curr
return curr- 초기값 설정 후 해당 목표까지 값을 더해 정답을 구했다.
앞서 작성한 코드를 봤을 때 직관적으로 규칙을 이해하기 어렵다고 생각되어 메모이제이션 기법으로도 풀어보았다.
class Solution:
def climbStairs(self, n: int) -> int:
memo = [1, 1]
for i in range(2, n+1):
memo.append(memo[i-2] + memo[i-1])
return memo[n]- 초기 배열 설정 후 앞의 두 값을 더한 값을 배열에 추가하며 계산했다.
