[LeetCode] 70. Climbing Stairs

문제 링크 : https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

1또는 2씩 계단을 오르는 모든 경우의 수를 리턴하는 문제이다.

가령 n 개의 계단이 주어졌을 경우 1칸 또는 2칸씩 올라갈 수 있는데 경우의 수가 모두 얼마인지 계산하면 된다. 

 

처음 생각했을 때는 1칸 올라가는 갯수를 a, 2칸 올라가는 갯수를 b라 가정하고 a에 n값을 넣은 뒤, a가 음수가 아닐때 까지 while 루프를 돌면서 a에서 2만큼 빼주고 -> 그만큼 b에 1씩 더해주면 된다고 생각했었다. 

 

처음 짠 코드는 아래와 같다. 

class Solution {
    public int climbStairs(int n) {
        int ans = 0;        
        if(n==1) {
            return 1;
        } 
        if(n==2) {
            return 2;
        }
        int a = n;
        int b = 0;
        int tmp = 0;
        while(a>=0) {
            a-=2;
            b+=1;
            tmp = 1*a + 2*b;
            if(n==tmp) {
            	ans++;
            }
        }
        return ans;
    }
}

그런데 생각을 해보니 문제가 있었다. 가령 4라고 한다면 while 루프를 돌면서

 

ans=1, a=4, b=0  → 1+1+1+1

ans=2, a=2, b=1 → 1+1+2

ans=3, a=0, b=2 → 2+2

 

이렇게 바뀌는데 ans=2인 부분에서 1칸 1칸 2칸 올라가는 경우의 수가 1개가 아니라 3개이다. 

1→2→4, 1→3→4, 2→3→4 이렇게 이기 때문이다. 

잘못 계산하였고 다시 생각해보기로 하였다. 

 

접근법을 한번 다시 생각해보기로 하였다.

가령 n=4 인 경우라면 이렇게 5개의 가짓수가 나오게 된다.

 

그런데 n=3, n=4, n=5일 때를 병렬로 그려보니까 패턴이 발견된 거 같긴 했다..!

이 부분을 한 번 활용해보면 어떨까? 하는 생각이 들었다. 

dp를 활용하여 n=1일 때 올라갈 가짓수, n=2일 때 올라갈 수 있는 가짓수 이렇게 해서 n까지 도달하는 형식으로 말이다...!

 

가령 n=4이라고 할 때를 다시 돌아가본다면, 2에서 올라오는 경우와 3에서 올라오는 경우 2가지가 있을 것이다. 1칸 또는 2칸 밖에 올라오지 못하기 때문 2에서 올라오는 경우라고 하면 2-3-4와 2-4이기 때문에 2개, 3에서 올라오는 경우는 3-4이기 때문에 그대로 더해주면 되지 않을까? 하는 생각이 들긴 했는데 점화식으로 쓸 수 있을지는 잘 모르겠다...ㅠㅠ 

 

그래서 생각을 해봤을 때 점화식은 다음과 같았다.

 

dp[n] = 2*dp[n-2] + dp[n-1]

 

그런데 이렇게 한다면 가령 n=4일 때 2에서 4로 올라가는 경우와 3에서 4로 올라가는 경우에서 경우의 수가 겹칠 때가 온다..dp[2]는 1-2 과 2의 두 경우를 포함하고 있고, dp[3]은 1-2-3, 1-3, 2-3 이렇게 두개를 포함하고 있기 때문에 위 점화식처럼 하면  1-2-3-4를 두번씩 더한 셈이 된다. 애초에 이전 값을 가져와서 더해주는 것이라 중복은 당연히 생기며 다른 방법이 필요하다.

 

그렇다면 이렇게 생각을 해보았다. n=4라고 가정할 때,  

(2에서 4까지 가는 경우의 수) + (3에서 4까지 가는 경우의 수) 이다. 

원래는 dp[3] -dp[2] 같이 가는 경우의 수를 빼고 dp[2]에서 *2를 했었다. 

dp[n] = dp[n-1] - dp[n-2] + 2*dp[n-2];

 

그런데 생각해보니 굳이 이렇게 어렵게 하느니 이전 계단과 그 이전 계단에서 올라가는 경우의 수를 더하기만 하면 된다. 굳이 어렵게 생각 안해도 된다.

dp[n] = dp[n-1] + dp[n-2];

 

이를 토대로 작성한 코드는 아래와 같다.

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