[C] LeetCode 70. Climbing Stairs

문제(영어)

 

문제(번역)

너는 계단을 오르고 있다. 꼭대기에 다다르려면 n 걸음이 걸린다.

한번에 1칸 또는 2칸 오를 수 있다. 정상에 다다르려면 몇가지 구별되는 방법이 있나요?

 

접근 방법

문제를 보자마자 DP가 생각났다.

정상이 1인 경우, 갈 수 있는 경우의 수는 1칸만 이동하는 1개 밖에 없다.

정상이 2인 경우, 1칸 이동하고 1칸을 이동하거나 바로 2칸을 이동하는 경우가 존재한다.

정상이 3인 경우, 1번째 칸에서 올라오거나 2번째 칸에서 올라올 수 밖에 없다.

 

즉, 정상 t에 오르기 위해서는 t-1에 오는 방법의 수와 t-2에 오는 방법의 수를 더하면 된다!

 

코드

int climbStairs(int n) {
    int array[46] = {0};
    array[0] = 0;
    array[1] = 1;
    array[2] = 2;
    if (n<3) return array[n];
    for(int i = 3; i<=n;i++) {
        array[i] = array[i-1] + array[i-2];
    }
    return array[n];
}

 

시간/공간복잡도

먼저 n의 범위에 맞게 array를 미리 만들어둔다. 그렇기에 공간복잡도는 O(n)이다.

또한 결국 n까지 반복문을 이용해 배열에 접근하므로 시간복잡도 역시 O(n)이 될 수밖에 없다.