Leetcode - 70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

 

처음에는 수학문제처럼 느껴졌었는데 n 칸의 계단을 1 이나 2 만큼씩 올라갈수 있을때 몇가지 방법 이있냐는 문제였다.

 

일단 dp 라는걸 모른다는 가정하에 (dp 문제 였지만 ;;) 노가다로 패턴을 찾기 시작했다.

 

n =1  ways = 1

n =2 ways = 2

n = 3 ways = 3

n = 4 ways = 5

n = 5 ways = 8

 

너무 힘들어서 더는 못하겠다 ㅠㅠ 

잉? 근데 뭔가 느낌이 피보나치 인거 같아서 이악물고 한번만 더 해봤다

n = 6 ways = 13 으로 피눈물을 흘리면 피보나치인걸 확인후 코드를 구상하기 시작했다.

 

일단 계단 오르기 전 n = 0, 첫번째 계단 n =1 을 각각 1로 두고 식을 시작했다. 

예를 들어 n =3 의 ways 를 구하려면 n = 1 의 ways + n = 2 의 ways 이니 loop 을 돌릴때 n -1 까지 돌리면 된다는걸 확인후 

for i in range (n - 1) 로 for loop 을 시작했다.

 

loop 안에서 해야할것은 일단 shift 를 한번씩 해주는것:

one 을 two 로 만들고 (오른쪽 한칸 이동)

two 를 one + two 로 만드는것이었다. (오른쪽 한칸 이동) 피보나치이기 때문

 

loop 이 끝나고 two value 를 리턴한다면 loop 이 끝났을때의 two value 즉 우리가 원하던 값이 나온다

 

class Solution:
    def climbStairs(self, n: int) -> int:
        one, two = 1, 1 
        for i in range (n-1):
            temp = two 
            two = one + two
            one = temp

        return two

문제의 비해서 코드가 쉬워서 당황스 ㅋㅋ