알고리즘: 웨브바짐 문제 분해 - 4 (완)

주어진 알고리즘을 직관적으로 생각하기 어렵다고 생각하여 문제를 4개의 작은 문제들로 분리해보았습니다.

먼저, 원본 문제의 링크입니다: https://algospot.com/judge/problem/read/ZIMBABWE

입력받은 양의 정수형 숫자 num에 대하여 각 자릿수의 숫자 순서를 바꾸어 나타낼 수 있는 모든 값들 중에서 num보다 작은 값을 갖고, 또 다른 주어진 입력 값 M의 배수인 값들을 모두 출력하라. 단, 자릿수들의 값은 서로 같을 수 있으며, (예: 2031, 4401, 5550016, 10348 등이 num으로 가질 수 있다), 2 <= M <= 20 을 만족한다.

해설: 이번 문제에서는 num의 모든 숫자들의 나열 중에서 num보다 작으면서, 입력 값 M과 나누어 떨어져야 합니다. 다수의 선택된 숫자들이 같고 num보다 작더라도 숫자 하나의 배치 차이로 인해 M과 나누어 떨어지거나 그렇지 않을 수 있습니다. 예를 들어, num = 2302 이고 M = 4 일때, 두 숫자 2032와 2023은 모두 앞의 두 숫자가 20이고 모두 num보다 작지만, 2032는 M으로 나누어 떨어지고 2023은 M으로 나누어 떨어지지 않습니다. 따라서, 매번 숫자를 선택할 때마다 taken과 isLess를 갱신하것과 더불어 현재 선택된 값들의 M으로 나눈 나머지 값들을 보관해야 합니다. 이 값을 remainder라고 할 때, taken과 isLess 그리고 remainder가 같다면 이후의 나오는 결과의 개수도 동일하다고 할 수 있습니다. 문제에서, 2 <= M <= 20이므로, cache는 다음과 같이 정의할 수 있습니다.

int cache[1 << 14][20][2];

매번 자리수 값을 선택할 때마다 remainder를 갱신해 주어야 하며, 모든 자리수의 숫자들을 선택했을 때, isLess = true이고 remainder = 0 이면 조건을 만족하는 숫자라고 할 수 있으므로 1을 반환하며, 그렇지 않으면 0을 반환합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#define MAXNUMBER 14
#define MOD 1000000007
 
vector<int> numVec;
vector<int> logVec;
vector<int> vec;
vector<bool> usedVec;
long long M = 0;
int cache[1 << MAXNUMBER][20][2];
 
int price(int idx, int remainder, int taken, bool isLess){
    int size = vec.size();
    if (idx == size){
        return (isLess && remainder == 0) ? 1 : 0;
    }
    int& cc = cache[taken][remainder][(int)isLess];
    if (cc != -1){
        return cc;
    }
    cc = 0;
    for (int i = 0; i < size; i++){
        if (usedVec[i])
            continue;
        if (!isLess && vec[i] > numVec[idx]){
            continue;
        }
 
        if (i != 0 && vec[i - 1] == vec[i] && !usedVec[i - 1])
            continue;
        logVec.push_back(vec[i]);
        usedVec[i] = true;
        int newTaken = taken | (1 << i);
        int newRemainder = (remainder * 10 + vec[i]) % M;
        bool newLess = isLess || vec[i] < numVec[idx];
        cc += price(idx + 1, newRemainder, newTaken, newLess);
        usedVec[i] = false;
        logVec.pop_back();
    }
    cc = cc % MOD;
    return cc;
}
 
void main(){
    int nrNum = 1 << MAXNUMBER;
 
    numVec.clear();
    vec.clear();
    usedVec.clear();
    long long num;
    cin >> num >> M;
    cout << "입력:" << num << "," << M << endl;
    int temp;
    while (num > 0){
        temp = num % 10;
        numVec.push_back(temp);
        vec.push_back(temp);
        usedVec.push_back(false);
        num /= 10;
    }
    sort(vec.begin(), vec.end());
    int halfSize = vec.size() / 2;
    int j = vec.size() - 1;
    for (int i = 0; i < halfSize; i++){
        temp = numVec[i];
        numVec[i] = numVec[j];
        numVec[j] = temp;
        j--;
    }
 
    for (int i = 0; i < nrNum; i++){
        for (int j = 0; j < M; j++){
            for (int k = 0; k < 2; k++){
                cache[i][j][k] = -1;
            }
        }
    }
    int answer = price(0, 0, 0, false);
    cout << "경우의수:" << answer << endl;
}

라인 38과 같이 반복문 내에서 특정 숫자를 선택한 직후에 지금까지 선택한 숫자들의 값에 대하여 M으로 나눈 나머지 값을 갱신합니다.

그리고 그 값을 price 함수의 매개변수로 넘겨줌으로써, 나중에 같은 숫자들이 선택되고, 모두 num보다 작으며, 나머지 값도 같을 때, 중복계산을 회피하고 cache에 저장된 경우의 수를 가져다 씀으로써 수행속도를 크게 높일 수 있습니다.

위의 그림은 분해3의 코드에 대하여 num = 12738173912를 입력으로 했을 때, num보다 작은 모든 경우의 수를 나타냅니다. 총 76228개가 결과로 출력됩니다.

위의 그림은 분해4의 코드에 대하여 num = 12738173912를 입력으로 했을 때, num보다 작으면서 M = 7로 나누어 떨어지는 모든 경우의 수를 나타냅니다. 

총 11033개가 결과로 출력된 것을 알 수 있습니다.