Leetcode - 70. Climbing Stairs (Easy)

이번 문제는 꽤 유명한 문제 입니다.

 

계단을 오르는 데 한번에 한 칸을 올라가거나 혹은 두칸을 올라갈 수 있습니다.

계단의 숫자를 입력값으로 받은 후 그 계단을 올라 갈 수 있는 방법은 몇가지가 있을 지 계산해야 합니다.

 

패턴을 한번 보겠습니다.

 

 

1. 계단이 1개 이면 방법은 1개 입니다.

2. 계단이 2개 이면 방법은 한 칸- 한 칸, 한번에 두칸 이렇게 두가지 방법이 있습니다.

3. 계단이 3개면 방법은 3가지 입니다. 1번 방법과 2번 방법을 더하면 됩니다.

일단 한칸 올라온 다음에 남은 방법은 나머지가 두칸이니까 2번에서 구한 2가 됩니다.

이단으로 두칸 올라온 다음에 남은 방법은 나머지가 한칸이니까 2번에서 구한 1이 됩니다.

그래서 1+2 =3 이 됩니다.

4. 그러면 4 칸 일 때는 3번과 2번을 더한 값인 5가 되겠죠.

일단 한칸 올라간 다음에 남은 방법은 나머지가 3칸이니까 3번에서 구한 3 가지 입니다.

이단으로 두칸 올라간 다음에 남은 방법은 나머지가 2칸 이니까 2번에서 구한 2가 됩니다. 

그러면 3+2인 5가 됩니다.

5. 계단이 5개 이면 당연하 4번 더하기 3번이겠죠. 그러면 5+3이 되서 총 8가지 방법이 있습니다.

 

이렇게 되면 공식을 구할 수 있죠.

 

N(current) = N(previous) + N(previous-1) 이 됩니다.

 

이걸 로직으로 만들어서 코딩을 하면 됩니다.

 

저에게 가장 쉬운 방법은 아래 방법입니다.

 

class Solution {
    public int climbStairs(int n) {
        if(n <=2) return n;
        
        int prev1 = 1;
        int prev2 = 2;
        int cur= prev1 + prev2;
        
        while(n>=3) {
            cur = prev1 + prev2;
            prev1 = prev2;
            prev2 = cur;
            n -= 1;
        }
        return cur;
    }
}

 

실행 결과는 아래와 같습니다.

다른 설명서 보니까 이런 방법도 있던데...

 

class Solution {
    public int climbStairs(int n) {
        return climb_Stairs(0,n);
    }
    
    public int climb_Stairs(int i, int n) {
        if (i > n) {
            return 0;
        }
        
        if(i == n) {
            return 1;
        }
        
        return climb_Stairs(i+1, n) + climb_Stairs(i+2, n);
    }
}

 

이해하기도 어렵고 별로 좋은 방법인 것 같지는 않습니다.

 

Runtime을 조금 더 줄이려면 아래 방법이 있습니다.

 

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

 

이런 방법도 있고요.

 

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

 

Runtime은 모두 비슷하고 바로 위 코드가 메모리를 조금 덜 차지하는 것 같습니다.

 

그 다음에 제가 이해하기 힘든 코드는 아래 두가지가 있습니다.

수학 공식을 사용하던데...

 

 public class Solution {
    public int climbStairs(int n) {
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n);
        return res[0][0];
    }
    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }
    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
}

 

그리고

 

public class Solution {
    public int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double phi = (1 + sqrt5) / 2;
        double psi = (1 - sqrt5) / 2;
        return (int) ((Math.pow(phi, n + 1) - Math.pow(psi, n + 1)) / sqrt5);
    }

어쩄든 제가 만든 첫번째 스크립트하고 Runtime하고 Memory 결과 값은 비슷하더라구요.

 

첫번째 제가 시도한 방법은 Fibonacci Number라고 합니다.

 

Fibonacci Number에 대해 나중에 한번 살펴 봐야 겠습니다.

오늘은 이만......