HackerRank : Davis' Staircase

문제 링크

HackerRank : Davis' Staircase (Click)

문제 요약

1. Davis의 집에는 계단이 많은데, Davis는 한번에 계단을 오를때 1칸, 2칸, 또는 3칸을 오를 수 있다.
2. Davis가 n층 높이의 계단을 오를때, 몇 가지의 가지수로 계단을 오를 수 있는지 정답을 구하라.
3. 이때 정답은 10000000007로 나눈 나머지를 출력하라.

문제 풀이

    public static int stepPerms(int n) {
        if(n == 0) return 0;
        else if(n == 1) return 1;
        else if(n == 2) return 3;
        else if(n == 3) return 4;

        int t1 = 1;
        int t2 = 2;
        int t3 = 4;
        int res = 0;


        for(int i=0; i<n-3; i++) {
            res = t1 + t2 + t3;
            t1 = t2;
            t2 = t3;
            t3 = res;
        }

        return res;
    }

전형적인 DP문제이다.
계단을 1개 오르는 경우, 2개 오르는 경우, 3개 오르는 경우의 기본 값을 구한 뒤, 주어진 계단수에 맞춰 (n-3) + (n-2) + (n-1)의 경우의 수를 구하면 된다.

시간복잡도

O(n). 단, 굳이 디테일하게 말하자면 O(n-3)