BOJ 1040 정수

* BOJ 1040 정수

[분류 : 비트마스크, 다이나믹 프로그래밍]

  BOJ 3026 V(링크: https://www.acmicpc.net/problem/3026, 풀이 링크: https://coloredrabbit.tistory.com/110)을 먼저 풀 것을 권장합니다.

[풀이]

  1. [사용할 수 있는 숫자의 수는 K] 이것이 시사하는 바는 총 10개의 숫자 중 K개만을 선택하여 계산하겠단 소린데 경우의 수로 따지면 아무리 커봐야밖에 되지 않습니다.

  2. [백트래킹이 안되는 이유] 뭐 당연하겠지만 K개 골라봤자, 수의 길이가 최대 18까지 올라갈 수 있고, 거기서 K^18 경우의 수가 나올 수 있으므로 시간이 모자랍니다.

  3. [자리수 dp] 

  높은 자리에서 낮은 자리로 내려가며 N과 똑같은 자리수에 똑같은 숫자를 놓는 상황을 생각해보자. 가령 N=45523이고 10^2자리까지 똑같이 구성했다고 생각해보자. 그러면 현재 455까지는 똑같고 사용한 숫자의 수는 2가 된다. 이 때 여기, 10의 자리수에서 승부를 본다면 3이상의 수를 골라야한다. 따라서 똑같은 자리수에 똑같은 숫자를 구성해왔음을 나타내는 플래그 변수가 필요하다.

  위와 다르게 승부를 이미 본 상황에서는 어떻게 될까. N보다 큰 수 중 가장 작은 값을 가져와야한다.

[상황1 - 이미 K개를 다 썼다] - 고른 K 숫자에서 가장 작은 숫자로만 채워주면 된다.

[상황2 - K개를 다 쓰지 않았다] - 사용하지 않은 숫자 중에서 가장 작은 숫자부터 사용해나가면 된다.

  4. [자리수가 클 수도 있다]

  가령 주어진 수가 99999이고 K가 2 이상이라면 5자리로 절대로 구성할 수 없습니다. 이 때는 N을 10의 제곱수로 설정하고 진행하면 비교적 쉽게 처리 가능합니다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
using ll = long long;
int dp[2][1 << 10][18], L, c;
int rec(int l, int s, int d, int* A) {
    if (d == L)
        return c == 0;
    int& ret = dp[l][s][d];
    if (ret != -1) return ret;
    ret = 0;
    int i, S = l ? A[d] : 0;
    for (i = S; i < 10; i++) {
        if ((1 << i) & s)
            ret |= rec(l && i == S, s, d + 1, A);
        else if (c) {
            c--;
            ret |= rec(l && i == S, s | (1 << i), d + 1, A);
            c++;
        }
    }
    return ret;
}
void f(int l, int s, int d, int* A) {
    if (d == L) return;
    int& ret = dp[l][s][d];
    int i, S = l ? A[d] : 0;
    for (i = S; i < 10; i++) {
        if (((1 << i) & s)) {
            if (rec(l && i == S, s, d + 1, A)) {
                printf("%d", i);
                f(l && i == S, s, d + 1, A);
                break;
            }
        }
        else if (c) {
            c--;
            if (rec(l && i == S, s | (1 << i), d + 1, A)) {
                printf("%d", i);
                f(l && i == S, s | (1 << i), d + 1, A);
                break;
            }
            c++;
        }
    }
}
int main() {
    int K, A[18], i;
    ll N, t;
    scanf("%lld%d", &N, &K);
    t = N;
    for (i = 0; t; i++) {
        A[i] = t % 10;
        t /= 10;
    }
    L = max(i, K);
    if (i >= K) {
        for (i = 0; i < L / 2; i++) {
            t = A[i];
            A[i] = A[L - 1 - i];
            A[L - 1 - i] = t;
        }
    }
    else {
        A[0] = 1;
        for (i = 1; i < L; i++) A[i] = 0;
    }
    c = K;
    memset(dp, -1, sizeof dp);
    if (rec(1, 0, 0, A))
        f(1, 0, 0, A);
    else {
        A[0] = 1;
        L++;
        for (i = 1; i < L; i++) A[i] = 0;

        memset(dp, -1, sizeof dp);
        rec(1, 0, 0, A);
        f(1, 0, 0, A);
    }

    return 0;
}