풀이_LC70.md

🫖 70. Climbing Stairs

• Date : 2021.11.14(일)
• Time : 10분

Problem

• 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?

Constraints

• 1 <= n <= 45

Example

• Input: n = 3
• Output: 3
• Explanation: There are three ways to climb to the top.

  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step
  

풀이

    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        first, second = 1, 2

        for i in range(3, n + 1):
            first, second = second, second + first

        return second

: 1걸음 또는 2걸음을 올라갈 수 있다. 이때 n만큼의 계단을 걸으려면 몇개의 방법이 있는지 나타내는 문제이다. 계단이 2개가 있을때마다 방법은 2개가 생긴다. 1+1 혹은 2. 무조건 이렇게 밖에 생기지 않는 점을 이용했다.