[LeetCode/Kotlin]Easy - 70. Climbing Stairs

[LeetCode/Kotlin]Easy - 70. Climbing Stairs

Climbing Stairs - LeetCode

문제

---

 

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의 모든 경우의 수를 구하면 되겠다고 생각했다. 다 풀고 제출하니 ‘45’ 에서 시간 초과가 났다. 재귀는 안된다 ?

그때부터 살짝 멘붕이었다. 당연히 이렇게 풀면 될거라고 생각해서 골랐던 문제였다. 그래서 모든 테스트 케이스를 돌려봤다. 그랬더니 규칙이 보였다.

앞에 두개의 숫자를 더하면 다음 숫자가 나타난다. 피보나치 수열이다. 그래서 나는 그냥 간단하게 배열을 만들어 해당하는 index에 차곡차곡 계산해서 넣었고, n의 위치값을 리턴했다.

최종 소스코드

class Solution {
    fun climbStairs(n: Int): Int {
        val sum = Array(n+1) { 0 }
        for (i in 1 .. n) {
            if (i == 1) sum[1] = 1
            else if (i == 2) sum[i] = 2
            else sum[i] = sum[i-2] + sum[i-1]
        }
        return sum[n]
    }
}

1. Array를 n+1 크기로 만든다. n이 2인 경우, 바로 array[n]으로 불러올 수 있도록 [0] 번째 인덱스는 사용하지 않을 것이다.
2. n이 1인 경우 값은 1이다.
3. n이 2인 경우 값은 2이다.
4. 3부터는 앞에 두개의 값을 더한 값을 저장한다.
5. n에 해당하는 값을 리턴한다.

다른 풀이법

fun climbStairs(n: Int): Int {
    if (n <= 2) {
        return n
    }
    
    var prev1 = 1
    var prev2 = 2
    
    for (i in 3..n) {
        val current = prev1 + prev2
        prev1 = prev2
        prev2 = current
    }
    
    return prev2
}

위 풀이처럼 굳이 배열을 쓸 필요 없이 prev 값만 엎어쳐줘서 그때그때 계산해도 된다.