쉬운 계단 수 ( 10844 번 )

10844번: 쉬운 계단 수

 

---

🧠 알고리즘

• 동적 계획법(DP)

 

✔️ 동작 방식

• dp[length][last_digit] = 길이 length인 계단 수 중 마지막 숫자가 last_digit인 개수
• 길이 1 초기값 설정 (dp[1][1~9] = 1, dp[1][0] = 0)
• 점화식:
  • last_num > 0 → 이전 숫자가 last_num-1인 수 더하기
  • last_num < 9 → 이전 숫자가 last_num+1인 수 더하기
• 길이 n까지 계산 후 합산 → 결과

---

 

🧾 코드

import sys

def _main(n):
    """
        dp[시행 횟수][마지막 숫자]
    """
    dp = [[0] * 10 for _ in range(n + 1)]
    dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    for idx in range(2, n + 1):
        for last_num in range(10):
            if last_num > 0:
                dp[idx][last_num] += (dp[idx - 1][last_num - 1] % 1000000000)
            if last_num < 9:
                dp[idx][last_num] += (dp[idx - 1][last_num + 1] % 1000000000)
    
    return sum(dp[-1]) % 1000000000

n = int(sys.stdin.readline().rstrip())
print(_main(n))

---

 

⏱️ 시간 복잡도

for idx in range(2, n + 1) : 길이 만큼 반복 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )