[ LeetCode - 70 ] Climbing Stairs

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

Climbing Stairs - LeetCode

 

규칙을 찾다가 보면 피보나치 수열이 나오게 된다.

[ 규칙 찾기 ]

5번째 계단이 왜 8일까?

계단을 올라갈 수 있는 방법은 총 2가지 밖에 없다. (1칸 or 2칸)

8까지 도달하기 위해서는 3번째 계단(3)에서 2칸 그리고 4번째 계단(5)에서 1칸 올라가는 방법뿐이기 때문에 3 + 5 총 8가지 방법이 나오게 된다.

 

이 규칙은 피보나치 수열과 일치하기 때문에 피보나치 수열 문제라고 봐도 무방할 것 같다.

 

[ 📌 풀이 ]

1. 주어진 정수 n을 이용해서 피보나치 배열을 만든다.

2. 피보나치 수열의 0, 1번 인덱스의 값을 0, 1로 설정한다. (피보나치 수열은 index - 2 + index - 1 이기 때문에 앞의 두 값이 필요)

3. 완성된 수열에서 필요한 값 return

 

[0, 1, 1, 2, 3, 5, 8, 13]

반복문이 돌아간 후 배열은 이런식으로 만들어진다.
앞의 0 대신 1, 1로 초기화 하고 돌려도 상관 없다.

 

[ 📌 코드 - Python ]

class Solution:
    def climbStairs(self, n: int) -> int:
        fibo = [0 for _ in range(n + 2)]
        fibo[1] = 1

        for idx in range(2, n + 2):
            fibo[idx] = fibo[idx - 2] + fibo[idx - 1]

        return fibo[n + 1]

s = Solution()
result = s.climbStairs(6)

print(result)

 

[ 📌 결과 ]

[ Result ]