백준 [11057]: 오르막 수

📌 백준 [11057]: 오르막 수

🔗 문제 링크

---

문제 설명 📄

수의 자릿수가 N이고, 각 자릿수가 0부터 9까지 증가하는 수를 오르막 수라고 한다.
N이 주어졌을 때, 오르막 수의 개수를 10007로 나눈 나머지를 구하시오.

---

문제 접근 방식 💡

• DP 테이블 dp[i][j]를 정의:
  • i: 자리 수
  • j: 마지막 자릿값이 j인 오르막 수의 개수
• 점화식:
  • dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + ... + dp[i-1][9]
• 최종 결과:
  • sum(dp[n-1]) % 10007

---

Solution 💻

n = int(input())

dp = [[1] * 10 for _ in range(n)]

for i in range(1, n):
    for j in range(10):
        dp[i][j] = sum(dp[i - 1]) - sum(dp[i - 1][0:j])

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

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n × 10 × 10)
  • n번 반복, 내부에서 j와 관련된 합 계산에서 최대 10번씩 반복.
  • 더 효율적인 계산 방법이 존재함.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n × 10)
  • DP 테이블의 크기가 n × 10.

---

리팩토링 🛠️

해당 코드에서 sum(dp[i - 1])를 중복 계산하는 비효율이 존재합니다. 이를 누적합을 활용하여 최적화 가능합니다.

n = int(input())

dp = [[1] * 10 for _ in range(n)]

for i in range(1, n):
    for j in range(10):
        dp[i][j] = sum(dp[i - 1][j:])

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

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n × 10)
  • 각 i에 대해 j는 고정된 범위(10)에서 연산 수행.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n × 10)
  • DP 테이블 크기는 동일.