[백준(BOJ)] 11057번: 오르막 수 (Dynamic Programming, C++)

📝 문제풀이 과정

---

• i는 1 ~ N까지, j는 0 ~ 9까지 범위
• N = 1
  • 한 자리일 때 
  • 0 ~ 9 (10가지)
• DP[i][j] = DP[i-1][k]
  • DP[i][j](i번째 자릿수일 때, j 숫자가 올 때)는 이전(i-1)은 해당 수(i)보다 작은 수부터 해당 수(k<=j)까지 가능하다.
  • 이 DP[i-1][k]에 대한 0 ~ j까지의 경우를 DP[i][j]에 순차적으로 더해준다.
  • 이후 DP[i][j] % 10007을 진행한다.

 

 

💻 C++ 제출코드

---

#include <stdio.h>

int main(){
    int N;
    scanf("%d", &N); // N: length of number

    int DP[N+1][10] = {};

    for(int i=0; i<10; i++) DP[1][i] = 1;

    for(int i=2; i<=N; i++){ // 자릿수
        for(int j=0; j<10; j++){
            for(int k=0; k<=j; k++){ // 0 ~ 9 수에 대한 경우
                DP[i][j] += DP[i-1][k];
            }
            DP[i][j] %= 10007;
        }
    }
    int sum=0;
    for(int i=0; i<10; i++){
        sum = (sum + DP[N][i]) % 10007; 
    }
    printf("%d", sum % 10007);
}

 

 

👏 결과

---