[Code Tree] 계단 오르기 [Python]

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-climbing-stairs/description

계단 오르기 설명 | 코드트리

 

---

풀이

문제 요약

주어진 규칙대로만 계단을 오를 수 있을 때, N층 높이의 계단을 오르는 모든 경우의 수를 구하자.

아이디어

점화식은 다음과 같다.

dp[i] : i 번째 계단을 오르는 모든 경우의 수

계단은 2칸 또는 3칸씩만 오를 수 있으므로, 현재 계단까지 오르기 위해서는 2/3칸 낮은 계단에서 올라오는 경우의 수만 존재하기 때문이다.

• dp[i] = 1, { N = 2 or 3 }
• dp[i] = 0, ( N = 1 )
• dp[i] = dp[i - 2] + dp[i - 3]

수가 너무 커질 수 있으니, 1e4 + 7로 나눈 나머지를 출력하자.

n = int(input())

# Please write your code here.

def solve(N):
    if N <= 3:
        return 1
    
    MOD = int(1e4) + 7
    dp = [0] * (N + 1)
    dp[2] = 1
    dp[3] = 1
    for i in range(4, N + 1):
        dp[i] = (dp[i - 2] + dp[i - 3]) % MOD
    
    return dp[N]

print(solve(n))

풀이시간

5분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/code-tree/Algorithm Intro/DP I/02 계단 오르기(challenge-climbing-stairs).py

problem-solving/code-tree/Algorithm Intro/DP I/02 계단 오르기(challenge-climbing-stairs).py at main · rogi-rogi/problem-so