백준 11057번 오르막 수

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

슬슬 동적계획법에 대해 감을 잡아가는 것 같습니다!

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MOD = 10007;

 

int N;

int cache[10][1001]; //시작하는 숫자(0~9), N<=1000

 

int uphill(void)

{

        memset(cache, 0, sizeof(cache));

 

        for (int i = 0; i < 10; i++) //초기값

               cache[i][1] = 1; //0~9까지 하나씩

 

        //j부터 9까지의 i-1 길이의 오름수들을 더하면

        //j부터 시작하는 i 길이 오름수를 구할 수 있다

        for (int i = 2; i <= N; i++)

               for (int j = 0; j < 10; j++)

                       for (int k = j; k < 10; k++)

                       {

                              cache[j][i] += cache[k][i - 1];

                              cache[j][i] %= MOD; //여기서도 MOD로 나눈 나머지를 저장하는 것이 포인트

                       }

       

        int sum = 0;

        for (int i = 0; i < 10; i++)

               sum += cache[i][N]; //0~9로부터 시작하는 오름수를 모두 더하고

        return sum % MOD; //MOD로 나눈 나머지 출력

}

 

int main(void)

{

        cin >> N;

        if (N < 1 || N>1000)

               exit(-1);

 

        cout << uphill() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~