백준 11057번 [오르막 수](C++) -yes6686- 티스토리

백준 문제 풀이: 11057 [오르막 수]

---

문제 링크: https://www.acmicpc.net/problem/11057

문제 설명:

오르막 수는 자릿수의 숫자가 증가하는 형태를 가진 수입니다. 예를 들어, 2234나 111은 오르막 수입니다. 길이가 N인 오르막 수의 개수를 계산하는 문제입니다.

다음 조건이 적용됩니다:

• N은 1 이상 1000 이하의 정수입니다.
• 결과는 10007로 나눈 나머지를 출력합니다.

---

문제 해결 코드

#include <iostream>
#define MOD 10007
using namespace std;

int dp[1001][10]; // dp[length][digit]: 길이가 length이고 마지막 숫자가 digit인 오르막 수의 개수

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 수의 길이
    cin >> n;

    // 길이가 1일 때 초기값 설정
    for (int i = 0; i <= 9; i++) {
        dp[1][i] = 1;
    }

    // 동적 프로그래밍으로 오르막 수 계산
    for (int length = 2; length <= n; length++) {
        for (int digit = 0; digit <= 9; digit++) {
            for (int prev = 0; prev <= digit; prev++) {
                dp[length][digit] += dp[length - 1][prev];
                dp[length][digit] %= MOD;
            }
        }
    }

    // 길이가 n인 모든 오르막 수의 합 계산
    int ans = 0;
    for (int i = 0; i <= 9; i++) {
        ans += dp[n][i];
        ans %= MOD;
    }

    // 결과 출력
    cout << ans << '\n';

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 오르막 수를 계산합니다. 오르막 수의 성질(현재 자릿수의 숫자가 이전 자릿수의 숫자 이상)을 이용합니다.
• 구현 세부사항:
  • dp[length][digit]: 길이가 length이고 마지막 숫자가 digit인 오르막 수의 개수를 저장합니다.
  • 이전 자릿수 prev가 현재 자릿수 digit 이하인 경우만 누적합니다.
  • 모든 계산에서 10007로 나눈 나머지를 사용하여 결과를 유지합니다.
• 시간 복잡도 분석: O(N × 10 × 10) = O(1000 × 100)
  • N: 수의 길이
  • 10: 숫자의 범위 (0부터 9까지)

---

결과

길이가 N인 오르막 수의 개수가 정확히 출력됩니다. 동적 프로그래밍의 효율성과 오르막 수의 특성을 활용한 풀이입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!