오르막 수 - 11057번 백준

문제

문제 난이도 : 실버 1

문제 분류 : 다이나믹 프로그래밍

 

문제 리뷰

나머지 연산 생각해볼 필요가 있을 듯 하다

 

문제 소스코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <memory.h>

using namespace std;

long long DP[1001][10];

void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);
}



int main()
{
    Init();
    int n;
    cin >> n;
    for (int i = 0; i < 10; i++) {
        DP[1][i] = 10 - i;
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10; j++) {
            DP[i][0] = (DP[i][0] + DP[i - 1][j]);
        }
        for (int j = 1; j < 10; j++) {
            DP[i][j] = (DP[i][j - 1] - DP[i - 1][j - 1]) ;
            
        }
        for (int j = 0; j < 10; j++) {
            DP[i][j] %= 10007;
            //cout << DP[i][j] << " ";
        }
        //cout << endl;

    }

    cout << DP[n][0] % 10007 << endl;



}