LeetCode) 70. Climbing Stairs

계단 올라가는 경우의 수를 구하는 문제.

Language: java

class Solution {
    public int climbStairs(int n) {
        int sum = 0;
        
        if(n == 1) return 1;
        if(n == 2) return 2;
        
        sum = climbStairs(n-2) + climbStairs(n-1);
        return sum;
    }
}

다 써보고 나면 알겠지만, 결국 피보나치 문제였다.
알고리즘 문제를 왜 풀어보라는 지 알겠던 문제 ...
근데 문제가 하나 생겼다.
마지막 수인 45를 넣으면 Time Limit Exceeded 에러가 뜬다.
이유가 뭐지 ... ?

근데 구글링을 해보니 나같은 문제가 발생한 사람이 한 둘이 아니었다.
그래서 찾은(베낀) 해결책은 배열을 지정해주는 것이다.

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

위에서 의문을 품었던 걸 해소할 수 있다.
무작정 sum으로 넣고 돌리면, 계속 재귀 돌 때마다 더해주고 찾아가고 해야하니까 시간이 오래걸리는 것이다.

n의 값도
45까지라고 지정해줬기에, 크기가 45인 배열을 미리 만들어두고, n에 해당하는 값을 미리 담아주고, 재귀 돌 때 그 값을 빼서 쓰면 되는 것!!
훨씬 시간도 단축되고 좋은 방법인 듯 하다.

하 이렇게 완전 연관없어 보이는 문제에서 피보나치구나!를 알아채려면 대체 얼마나 오래, 많이 문제를 풀어봐야하는 걸까 ... 반성 + 감탄중 ㅠㅠ