[Java] 70. Climbing Stairs

문제 설명 :
1칸 또는 2칸씩 계단을 오를 수 있는데, 계단 수가 주어지면 몇 번의 경우의 수로 계단을 오를 수 있는지 도출하는 문제
 
 
- 처음코드

class Solution {
    public int climbStairs(int n) {
        int result = 0;
        int quotient = n/2;

        for(int i=0; i<=quotient; i++){
            result += conbination(n-i, i);
        }

        return result;

    }

    private int conbination(int x, int quotient){
        if (quotient == 0) return 1; // factorial에서 0! 주의!

        return factorial(x)/(factorial(x-quotient)*factorial(quotient));
    }

    private int factorial(int x){
        int result = 1;

        for(int i=1; i<=x; i++){
            result = result*i;
        }

        return result;
    }
}

 
- 동적계획법을 적용한 코드

class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;

        int[] step = new int[n+1];

        step[1] = 1;
        step[2] = 2;

        for(int i=3; i<=n; i++){
            step[i] = step[i-1] + step[i-2];
        }

        return step[n];

    }
}

해설 :
- 처음에는 경우의 수를 계산해서, 조합으로 처리하면 될 것 같아 factorial과 combination을 구현해 처리하였다.
- 초기 테스트 케이스는 통과하였는데, 다른 케이스들에서 문제가 생겨 알아보니 "동적계획법" 이라는 방식으로 해결해야하는 문제였다.
- 동적계획법으로 해결하는 문제가 처음이라 처음엔 다소 당황스러웠는데, 사실 상 수열과 확률을 해결할 때와 비슷했다.
- 예를들어 계단이 4개라고 하면, 우리는 처음에 1개의 계단을 오르고 3개의 계단을 갈 수 있고, 또는 2개의 계단을 오르고 나머지 2개의 계단을 갈 수 있다.
- 처음에 따라서 4개의 계단을 가는 것은 3개의 계단을 가는 방법과 2개의 계단을 가는 방법의 합으로 나타낼 수 있는데, 여기서 오랜만에 수학적 지식을 생각해보려고 하니 약간 띠용했다.
- 결국 처음에 1개를 갈지, 2개를 갈지는 경우의 수가 붙는게 아니라 내가 임의의 조건을 추가하는거라 카운트되지 않고 이런 조건에 따르는 결과에 대한 경우의 수를 합하면 되는 것이다.
- 따라서 step[n] = step[n-1] + step[n-2] 라는 점화식을 도출할 수 있다.