[Mock] Random 16

둘다 easy~...

---

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?

My Answer 1: Time Limit Exceeded (16 / 45 test cases passed.)

class Solution:
    def climbStairs(self, n: int) -> int:
        def choose(n,k):
            if k == 0:
                return 1
            elif n < k:
                return 0
            else:
                return choose(n-1, k-1) + choose(n-1, k)
        
        ans = 1
        
        for i in range(1, n//2+n%2):
            ans += choose(n-i, i)
        
        if n % 2 == 0:
            ans += 1
        
        return ans

재귀로 했는데... 타임리밋

2 의 개수에 따른 조합을 구함 => (n - 2의 개수) C (2의 개수)

머리가 넘 안돌아갔다...

Solution 1: Accepeted (Runtime: 48 ms - 6.69% / Memory Usage: 14.1 MB - 89.66%)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1 or n ==2:
            return n
        s1 = 1
        s2 = 2
        for i in range(2,n):
            s2 += s1
            s1 = s2 - s1
        return s2

피보나치로~

Solution 2: Accepeted (Runtime: 36 ms - 6.69% / Memory Usage: 14.3 MB - 42.14%)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        
        dp = [0]*(n+1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n+1):
            dp[i] = dp[i - 1] + dp[i - 2]
            
        return dp[n]

똑같은데 dp 로 한 것~

외우자 외우자

---

258. Add Digits

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

My Answer 1: Accepted (Runtime: 32 ms - 66.32% / Memory Usage: 14.2 MB - 71.20%)

class Solution:
    def addDigits(self, num: int) -> int:
        while num // 10 != 0:
            tmp = list(str(num))
            ans = 0
            for i in range(len(tmp)):
                ans += int(tmp[i])
            num = ans
        
        return num

한자리수가 될 때까지 각 자리수들을 더해주기