11057번 : 오르막 수 [C++]

문제 링크

성공 여부(걸린 시간): 성공(9분)

아이디어

해당 문제는 오르막 수 2를 풀어본 사람이라면 웃으면서 풀 수 있는 문제이다.

일단 주의할 점은 인접한 수가 같더라도 오르막 수 이고

한자리 수도 전부 오르막수로 간주된다.(그래서 1을 입력하면 10임)

 

dp [자릿수][해당 자릿수에 위치한 수 : 0~9 사이의 숫자]

그렇게 한다면 

3중 for문으로 

자릿수{

    이전 자릿수의 작은 수{

        현재 자릿수의 크거나 같은 수{
			dp[i][k] = (dp[i][k] + dp[i-1][j]) % 10007;
        }

    }

}

 

이렇게 해주면 끝

풀이 코드

#include<iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int dp[1001][10] = { {0,}, };
    int N;
    cin >> N; 
    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 = j; k < 10; k++) {
                dp[i][k] = (dp[i][k] + dp[i-1][j]) % 10007;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < 10; i++) {
        sum = (sum + dp[N][i]) % 10007;
    }
    cout << sum;
    return 0;
}