[코드트리/INTERMEDIATE LOW] DP I 계단 오르기 Python

🔥 문제 링크

https://www.codetree.ai/missions/2/problems/climbing-stairs?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔥 문제 

 

 

🔥 풀이

✅ 2칸 혹은 3칸으로만 올라갈 수 있으므로 1층을 갈 수 있는 방법 0개, 2층을 갈 수 있는 방법 1개, 3층을 갈 수 있는 방법 1개라는 초기값을 얻을 수 있다.

 

✅ 2칸, 3칸으로 올라갈 수 있으므로 n층에 갈 수 있는 경우의 수는 n-2층에서 올라오는 경우의 수와 n-3층에서 올라오는 경우의 수를 합치면 된다는 걸 알 수 있다.

dp[num] = step(num-2) + step(num-3)

 

✅ dp 배열을 만들어서 각각의 층마다 올라갈 수 있는 경우의 수를 memoization 하고 이전에 이미 계산된 값이면 그 값을 리턴하도록 한다

 

⚠️ 마지막에 %10,007로 나누어야 한다는 조건을 잊지 말자

 

 

 

🔥 코드

n = int(input())

def step(num):
    if dp[num] != -1:
        return dp[num]
    
    if num == 0:
        return 0
    elif num <= 2:
        return 1
    
    dp[num] = step(num-2) + step(num-3)
    return dp[num]

dp = [-1]*n

print(step(n-1)%10007)