Climbing Stairs

problem

계단의 높이가 주어질 때, 올라갈 수 있는 경우의 수는?
(계단은 1칸 또는 2칸을 움직일 수 있다.)
https://leetcode.com/problems/climbing-stairs

solution

class Solution {
public:
    int climbStairs(int n) {
        int prev = 1, current = 1;
        for(int i = 1; i<n; i++)
        {
            int tmp = current;
            current = prev + current;
            prev = tmp;
        }
        return current;
    }
};

후기

처음에는 감이 안잡혀서 자세히 보다가, 계단을 올라갈 수 있는게 1칸 또는 두칸이므로 다음계단을 오르는건 그전의 계산한 값과 연관이 있다고 생각했다.

즉 n번째 계단을 오를 수 있는 경우의 수를 f(n)이라 하면,
f(n) = f(n-1) + f(n-2) 가 되는 것이다.
(한칸 전에서 한칸을 가거나 두칸전에서 두칸을 갈 수 밖에 없음)

n에다가 n+1을 대입하면
f(n+1) = f(n) + f(n-1) 이된다.

피보나치 수열이다!

처음에는 재귀로 짰다가 오류가 났다.
피보나치 수열의 경우에는 재귀로 짜는 것보다 for문으로 해결하는 것이 편하다. 재귀로 짜면 f(n)을 위해서 그전에 한 계산을 다시 하기 떄문에 계산량이 기하급수적으로 증가하기 때문이다.