[BOJ] 11057번 오르막 수(C++)

풀이 소요시간 : 15분

약점을 보완하기 위해서 DP 나 Greedy 문제도 풀어야한다.

숫자의 길이 N 이 주어지고 오르막 수의 갯수를 구하는 문제다. Map[1000][10] 배열을 선언하였다. i 인덱스는 i - 1 번째 자리임을 의미하고 j 인덱스는 i - 1 번째 자리에서 j 숫자를 선택함을 의미한다. 마지막으로 Map[i][j] 는 i - 1 번째 자릿수에서 j 숫자를 선택할 수 있는 총 경우의 수를 의미한다.

전체 코드

#include <iostream>
#include <vector>
using namespace std;

int N;
int Map[1000][10];
// Map[3][1] = Map[2][0] + Map[2][1]
// Map[3][2] = Map[2][0] + Map[2][1] + Map[2][2]

int main() {
    cin >> N;
    
    //첫 자리의 경우의 수 = 1 
    for(int i = 0; i < 10; i++)
    {
        Map[0][i] = 1;
    }
    
    for(int i = 1; i < N; i++)
    {
        int Sum = 0;
        for(int j = 0; j < 10; j++)
        {
            Sum += Map[i - 1][j];
            Sum %= 10007;
            Map[i][j] = Sum;
        }
    }
    
    int Sum = 0;
    for(int i = 0; i < 10; i++)
    {
        Sum += Map[N - 1][i];
    }
    cout << Sum % 10007 << '\n';
    
}