Climbing stairs
Clibing Stairs
문제
- n개의 계단
- 한 번에 1 or 2 계단 오름
- 중복되지 않는 계단을 오르는 방법 수
풀이
dp 문제라는 걸 알고 시작해서 어렵지 않을 것 같다..
n개의 리스트를 만들고
list[i]
에 list[i-1]+list[i-2]
를 넣는다.
1칸 전과 2칸 전의 계단을 밟은 경우의 수를 합산하여 구하는 것
list[0] = 1, list[1] = 1를 기본으로 주고 시작
class Solution:
def climbStairs(self, n: int) -> int:
stairs = [0 for _ in range(n+1)]
stairs[0] = 1
stairs[1] = 1
for i in range(2, n+1):
stairs[i] = sum(stairs[i-2: i])
return stairs[-1]
결과
혹시 시간을 줄일 수 있을까 싶어서, 리스트 대신 int 만 저장해봤는데 큰 차이는 없었다.
class Solution:
def climbStairs(self, n: int) -> int:
one = 1
two = 1
three = 1
for i in range(2, n+1):
three = one+two
one, two = two, three
return three
Author And Source
이 문제에 관하여(Climbing stairs), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@twinklesu914/Climbing-stairs저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)