[Algorithm]Baekjoon 2688번 : 줄어들지 않아

https://www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int t, n;
long long dp[66][10] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    for (int i = 0; i <= 9; ++i)
    {
        dp[1][i] = 1;
    }
 
    for (int i = 2; i <= 65; ++i)
    {
        for (int j = 0; j <= 9; ++j)
        {
            if (i == 65 && j == 1) break;
 
            for (int k = j; k <= 9; ++k)
            {
                dp[i][j] += dp[i - 1][k];
            }
        }
    }
 
    cin >> t;
 
    while (t--)
    {
        cin >> n;
 
        printf("%lld\n", dp[n + 1][0]);
    }
}

 

n자리 수의 오름차순개수(같은숫자도포함)을 구하는 문제이다.

규칙은 꽤 쉽게 찾을 수 있다.

 

두자리숫자 00부터 시작한다고 생각해보자.

맨 앞에 0을 두면, 뒤의 숫자는 '반드시' 맨 앞 숫자이상부터 시작할 수 있다.

즉, 00의 경우 맨 앞이 0이기 때문에 뒤의 숫자도 0부터시작한다.

만약 맨앞숫자가 5라면, 뒤의 숫자는 5부터시작해야 한다.

즉, 한자리숫자인데 5부터 시작하는 오름차순의 개수를 더해주면 된다.

 

한자리숫자이면서 5부터시작하는 오름차순의 개수는 1개이다. 한자리니까 5 자체가 딱 한가지의 경우의 수이다.

한자리숫자는 한자리숫자이기 때문에 각각의 0~9까지의 숫자가 각각의 경우의수이다. (딱 한가지)

그렇기 때문에 먼저 dp[1][0] ~ dp[1][9]를 1로 초기화해줬다.

 

dp테이블 정의는 다음과 같다.

dp[i][j] = i 자리수에서 j로 시작하는 오름차순의 개수. 

 

만약 dp[2][5]라면, 두자리숫자들 중에서 5로시작하는 오름차순의 개수를 의미하는 것이다.

그리고 dp[2][5]를 구하기위해서는, 맨 앞에 5를 뒀기 때문에 그 뒤에는 5부터시작하는 한자리숫자의 개수를 더해줘야 한다. 5부터시작하는 한자리숫자는 5,6,7,8,9. 즉, dp[2][5] = dp[1][5] + dp[1][6] + dp[1][7] + dp[1][8] + dp[1][9]가 된다.

 

이런식으로 dp[2][0] ~ dp[2][9]까지 전부 더한다면 55가 나온다.

 

dp[2][0] => 맨 앞에 0을 뒀으니, 뒤에 0부터 시작하는 1자리수 + 1부터시작하는 1자리수 + 2부터 시작하는 1자리수 ...........

                     -> 10개

dp[2][1] = > 맨 앞에 1을 뒀으니, 뒤에 1부터 시작하는 1자리수 + 2부터 시작하는 1자리수 + 3부터 시작하는 1자리수 .........

                      -> 9개

 

.

.

.

 

10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 => 55.

 

이런식으로 전부 업데이트해주면 된다.