백준 [10844]: 쉬운 계단 수

📌 백준 [10844]: 쉬운 계단 수

🔗 문제 링크

---

문제 설명 📄

길이가 N인 계단 수의 개수를 구하시오.
계단 수는 다음 조건을 만족하는 숫자이다:

• 숫자의 각 자릿수가 인접한 자릿수보다 1만큼 차이가 남.
• 0으로 시작하는 숫자는 계단 수가 아님.

결과를 1,000,000,000으로 나눈 나머지를 출력하시오.

---

문제 접근 방식 💡

• 동적 프로그래밍(DP)을 사용하여 길이가 N인 계단 수를 계산.
• dp[i][j]를 길이가 i이고 마지막 자릿수가 j인 계단 수의 개수로 정의.
• 점화식:
  • dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
  • 경계 조건:
    • j=0이면, dp[i][j] = dp[i-1][1]
    • j=9이면, dp[i][j] = dp[i-1][8]
• 초기값:
  • dp[1][j] = 1 (단, j ≠ 0).

---

Solution 💻

n = int(input())

dp = [[0] * 10 for _ in range(n + 1)]
MOD = 1000000000

dp[1][0] = 0
for i in range(1, 10):
    dp[1][i] = 1

for i in range(2, n + 1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i - 1][1]
        elif j == 9:
            dp[i][j] = dp[i - 1][8]
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

print(sum(dp[-1]) % MOD)

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n × 10)
  • 이중 반복문에서 n번의 외부 반복과 10번의 내부 반복 수행.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n × 10)
  • DP 테이블이 (n+1) × 10 크기로 사용됨.

---

리팩토링 🛠️

n = int(input())

MOD = 1000000000
prev = [0] * 10
curr = [0] * 10

for i in range(1, 10):
    prev[i] = 1

for i in range(2, n + 1):
    curr[0] = prev[1]
    curr[9] = prev[8]
    for j in range(1, 9):
        curr[j] = prev[j - 1] + prev[j + 1]
    prev, curr = curr, [0] * 10

print(sum(prev) % MOD)

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n × 10)
  • DP 계산은 동일하게 수행됨.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(10)
  • 현재와 이전 상태만 저장하여 공간 사용을 최적화.