70. Climbing Stairs

문제 설명

• 계단 칸 "n"이 주어지면 해당 칸을 오르는 경우의 수를 구하는 문제이다.(단, 한번에 한 칸 또는 두 칸만 올라갈 수 있다.)

나의 접근

피보나치 수열!

n번째 계단을 가는 경우를 f(n)이라고 가정하면,
f(n)은 f(n-1)에서 한칸 오르는 경우, f(n-2)에서 두칸 오르는 경우로 쪼개서 생각 할 수 있으므로 정리하면
f(n) = f(n-1) + f(n-2)의 형태가 된다.

시간 복잡도 이슈로 인해 실패한 방법(by recursion)

int climbStairs(int n) {
    if(n == 1 || n == 2){
        return n;
    }
    return climbStairs(n-1) + climbStairs(n-2); 
}

재귀로 접근을 하니까 시간 복잡도적인 측면에서 문제가 발생하였다.

배열로 새롭게 접근

int climbStairs(int n) {
    int nums[45] = {0,};

    nums[0] = 1;
    nums[1] = 2;

    for(int i = 2; i < 45; i ++){
        nums[i] = nums[i-1] + nums[i-2]; 
    }

    return nums[n-1];
}

위와 같이 배열로 접근시에는 시간 복잡도가 O(1)꼴이 나오므로 성공적으로 해결되었다.

더 좋은 방법

굳이 배열 불필요하게 공간을 차지할 필요가 없다!

int climbStairs(int n) {
    int a = 0, b =1 , c;

    for(;n;n--){
        c = a+b;
        a = b;
        b = c;
    }
    return c;
}

Keypoint 1
단지 n번의 반복문을 선언한다면,

for(int i = 0; i < n; i++)

와 같이 인덱스 값을 선언할 필요가 없다.

keypoint 2
단순하게 반복문 안에 있는 연산 과정 자체가 피보나치 수를 계산하는 과정이므로, 굳이 배열을 만들 필요가 없다