[LeetCode] 70. Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

Climbing Stairs

 

계단을 오르는 문제다.

우리는 계단을 오를때 1칸 또는 2칸을 올라갈 수 있다.

이때 N칸의 계단을 오르는 방법은 몇가지인지 알아내는 문제이다.

 

이 문제는 중학교정도부터 경우의 수 찾는 문제로 자주 나오던 문제다.

 

풀이는 아래와 같다.

계단이 1칸일때 1칸을 오르는 방법은 1칸만 오르는 경우 1가지다.=>S_1 = 1

2칸일 경우에는 1칸을 오르고 1칸을 오르는 것과 처음부터 2칸을 오르는 경우로 2가지다. => S_2 = 2

 

3칸인 경우를 보자.

처음 오를때 1칸을 오를지 2칸을 오를지 정할 수 있다.

1칸을 올랐다고 하자.

그렇다면 남은 칸은 몇칸인가? 2칸이다.

그럼 이를 오르는 방법은? 처음부터 2칸을 오르는 경우와 같다. =>S_2

 

처음에 2칸을 올랐다고 하자.

그렇다면 남은 칸은 1칸이고, 처음부터 1칸을 오르는 경우와 같다.=>S_1

따라서 3칸을 오르는 방법은 1칸을 오르는 경우 + 2칸을 오르는 경우 => S_3 = S_2+S_1 과 같다.

 

4칸을 오를땐

처음 1칸이면 3칸이남고, 처음 2칸이면 2칸이 남는다.

따라서 S_4 = S_3 + S_2 와 같다.

 

결국 쭉 보면 S_n = S_n-1 + S_n-2 가 된다.

이를 배열로 만들어 갖고 있다가 호출해주면 된다. (50개 까지 여유있게 만들려했으나 그러면 int 범위가 넘어 터진다.)

 

전체 코드는 아래와 같다.

 

class Solution {
public:
    int climbStairs(int n) {
        int arr[50] = {1,2,};
        for (int i=2; i<45; i++) arr[i] = arr[i-1] + arr[i-2];
        return arr[n-1];
    }
};