[백준 10573] 증가하는 수

문제

www.acmicpc.net/problem/10573

 

알고리즘

DP

 

풀이

해당 수가 증가하는 수 인지 판별하고, 증가하는 수라면 그 수보다 작은 증가하는 수를 찾는 문제입니다.

 

증가하는 수를 판별하는 건 어렵지 않으니 다음 문제인 개수를 찾는 문제를 생각해봅시다. 증가하는 수의 구조는 최적 부분 구조를 만족하게 됩니다. 현재의 수가 증가하는 수라면 맨 앞자리 하나를 제거한 수 또한 증가하는 수를 만족하기 때문입니다.

 

$cache [i][j]$= j부터 증가하는 수를 i자리 만들었을 때, 가능한 개수

 

$cache [i][j]$를 갖고 갱신할 수 있는 상태는 j이하의 수를 맨 앞자리에 붙이는 것입니다. 즉 다음 상태는

$cache [i+1][k]$ (단, k는 j이하의 수이다) 입니다. 

 

나머지의 아이디어는 다음과 같습니다. 123을 예시로 들겠습니다. 

 

1. 세 자리 수의 증가하는 수를 모두 구합니다. 이는 $cache [4][0]$과 동일합니다.
2. 첫 번째 숫자보다 큰 수에 해당하는 2로 시작하는 세 자리 수의 증가하는 수를 뺍니다.
3. 두 번째 숫자보다 큰 수에 해당하는 3으로 시작하는 두 자리 수의 증가하는 수를 뺍니다.
4. 세 번째 숫자보다 큰 수에 해당하는 4로 시작하는 한자리 수의 증가하는 수를 뺍니다.
5. 이 값은 123을 포함하므로 마지막에 123을 빼기 위해 -1을 수행합니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int tc, sl;
long long cache[100][11];//현재까지 만든 자리 수, 시작하는 수
string s;

int main() {
    FAST;

    for (int i = 0;i < 10;++i) cache[1][i] = 1;
    for (int i = 1;i <= 80;++i) {
        for (int j = 0;j < 10;++j) {
            for (int k = j;k >= 0;--k) {
                cache[i + 1][k] += cache[i][j];
            }
        }
    }

    cin >> tc;
    while (tc--) {
        cin >> s;
        sl = s.size();
        char prv = '0';
        bool isInc = true;
        for (auto x : s) {
            if (prv > x) {
                isInc = false;
                break;
            }
            prv = x;
        }
        if (!isInc) cout << -1 << '\n';
        else {
            long long ret = 0;
            ret += cache[sl + 1][0];
            for (int i = 0;i < sl;++i) {
                int num = s[i] - '0';
                for (int j = num+1;j < 10;++j) {
                    ret -= cache[sl - i][j];
                }
            }
            cout << ret-1<< '\n';
        }

    }
    return 0;
}