# Climbing Stairs 


class Solution:
    def climbStairs(self, n: int) -> int:
        before2,  before1 = 1, 1
        answer = before1
        
        for _ in range(1, n):
            answer = before1 + before2
            before2 = before1
            before1 = answer
        
        return answer

"""
걸린 시간: 9분

복잡도: n-1번만큼 반복하기 때문에 시간복잡도는 O(n)이고, 변수 3개를 매번 초기화해가며 활용하기 때문에 공간복잡도는 O(1)이다.

해설: i번째 칸으로 오는 경우의 수는 i-1번째 칸에서 1칸 올라오는 것과 i-2번째 칸에서 2칸 올라오는 경우이다.
두 가지 올라오는 방법이 서로를 포함하지 않기 때문에 두 가지 경우의 수를 더하면 된다.
"""