[LeetCode] 70번 - Climbing Stairs [Swift]

문제 링크

문제

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?

 

Example 1:

Input: n = 2

Output: 2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step

2. 2 steps

 

Example 2:

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

 

Constraints:

• 1 <= n <= 45

문제 풀이

이 문제는 사다리를 1, 2칸씩 올라갈 수 있는데 n칸만큼 이동하는 경우의 수를 구하는 문제였습니다. 간단히 말해서 1,2의 합으로 숫자를 만들 수 있는 경우의 수였습니다. 이때 1+2+2와 2+1+2는 다른 경우로 체크해줘야 했습니다. 이러한 조건을 가지고 n=5 일 때까지를 직접 구해보면 아래와 같습니다.

저는 여기까지 하고 규칙을 찾아낼 수 있었는데요, 바로 n의 값은 n-1, n-2일때의 값을 더한 값이라는 규칙을 알아낼 수 있었습니다.

이런 규칙을 사용해서 DP로 이를 처리해서 답을 구해주면 쉽게 풀 수 있었습니다~

소스 코드

class Solution {
    func climbStairs(_ n: Int) -> Int {
        
        var dp: [Int] = [0,1,2]
        
        for i in 3...45 {
            dp.append(dp[i-2]+dp[i-1])
        }
        
        return dp[n]
    }
}