BOJ 3001 이상한 문제

* BOJ 3001 이상한 문제

[분류 : 다이나믹 프로그래밍]

[풀이]

1. [각 자리수 합이 S인 개수]

  구간이 정해져 있으므로 1부터 B까지 합이 S인 것의 개수에서 0부터 A-1까지 합이 S인 것의 개수를 빼준다. 이렇게하면 똑같은 함수를 두 번 호출하는 꼴이 나온다. 

rec(limit, position, summation, A)

※ limit은 주어진 A보다 작은 경우만 세야하므로 제한을 두는 변수다.

  기저영역은 A보다 작은 자리수에 대해 숫자를 채웠고 남은 summation이 0이 되는 경우에 1 더해주면 된다.

2. [A보다 크거나 같고 B보다 작은 수 중 자리수 합이 S가 되는 가장 작은 정수]

  문제 조건에서 적어도 하나 이상의 수가 반드시 존재한다고 했으니 이 값은 A와 가장 가까운 정수를 출력해주시면 되겠다

rec2(limit, position, summation, A)

※ limit은 주어진 A보다 큰 경우만 세야하므로 두는 제한 변수다.(A-1을 넘겨서 호출하면 결국 A와 같거나 큰 경우를 가져온다)

  다소 어려운 점이 있다면 자리수가 자체가 증가할 수 있단 사실이다. 이는 자리수를 하나씩 늘려가면서 가능 여부를 판단해주면 된다. 가능한 자리수 중 가장 짧은 길이일 때 종료시키고 답을 도출해내면 된다.

(참고) 자리수 dp에 대해 연습하고 싶으시다면 BOJ 3026 V 문제를 푸는 것을 추천합니다. 이거 풀면 웬만한 거 다 풀지 않을까싶네요

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
using ll = long long;
const int MAX_S = 136, L = 16;
ll cdp[2][L][MAX_S];
int vdp[2][L][MAX_S];
stack<int> ans2;
ll rec(int l, int p, int s, int* A) {
    if (p == -1) return !s;
    ll& ret = cdp[l][p][s];
    if (ret != -1) return ret;
    ret = 0;
    int i, limit = min(s, l ? A[p] : 9);
    for (i = 0; i <= limit; i++)
        ret += rec(l && i == A[p], p - 1, s - i, A);
    return ret;
}
int rec2(int l, int p, int s, int* A) {
    if (p == -1) return !l && !s;
    int& ret = vdp[l][p][s];
    if (ret != -1) return ret;
    ret = 0;
    int i, limit = min(s, 9);
    for (i = l ? A[p] : 0; i <= limit; i++) {
        if (rec2(l && i == A[p], p - 1, s - i, A)) {
            ans2.push(i);
            return ret = 1;
        }
    }
    return ret;
}
int main() {
    memset(cdp, -1, sizeof cdp);
    memset(vdp, -1, sizeof vdp);
    int A[L] = {}, al, B[L] = {}, bl, S, i;
    ll a, b, ans1;
    scanf("%lld%lld%d", &a, &b, &S);
    a--;
    for (i = 0; a; i++) {
        A[i] = a % 10;
        a /= 10;
    }
    al = i;
    for (i = 0; b; i++) {
        B[i] = b % 10;
        b /= 10;
    }
    bl = i;
    ans1 = rec(1, bl - 1, S, B);
    memset(cdp, -1, sizeof cdp);
    ans1 -= rec(1, al - 1, S, A);
    printf("%lld\n",  ans1);
    while (!rec2(1, al - 1, S, A))
        al++;
    while (!ans2.empty()) {
        printf("%d", ans2.top());
        ans2.pop();
    }
    return 0;
}