알고리즘: 웨브바짐 문제 분해 - 3

  분해2에서 설명했듯이, 가장 큰 자릿수의 숫자부터 순서대로 선택할 때, 만약 i번째 까지 선택된 숫자들이 동일하다면, (예를들어, num=2030 일때, 앞에 20이 선택되었든 02가 선택되었든) 이후에 선택되어 나열될 수 있는 경우의 수는 동일합니다. (20->2003,2030...02->0203,0230) 따라서, 선택된 값 (예:02)들을 인덱스로 해서 가능한 나열의 수를 최초로 계산한 결과를 보관해두면, 나중에 같은 값(예:20)을 선택했을 때, 같은 인덱스를 참조하여 별도의 반복문 없이 빠르게 값을 얻을 수 있습니다.

  같은 숫자들의 집합에 대하여 같은 인덱스를 가지도록 하기 위해 다음과 같은 방법을 사용할 수 있습니다. n자리 숫자에 대하여 i번째 자릿수의 숫자를 선택했다고 하면 i번째 비트 값은 1, 그렇지 않으면 0으로 설정합니다. 예를 들어, num = 2003이라고 할 때, 오름차순으로 정렬한 값 digits = 0023이 되고, 이에 대응되는 초기 선택여부 값 taken = 0000이 됩니다. 여기서, 첫 번째 자릿수 값이 digits[0] = 0이 선택되었다고 하면, taken = 1000이 됩니다. 그리고, 두 번째 자릿수의 값이 digits[1] = 0이 선택되었다고 하면, taken = 1100이 됩니다. 이런식으로 taken 값을 설정해주게 되면, 어떤 순서로 값을 선택하더라도 taken은 같은 값을 가지게 됩니다.

  이렇게 얻은 taken을 사용하여 미리 계산한 경우의 수들을 보관한 리스트에 접근하기 위해, 배열을 생성해야 합니다. 여기서, taken의 모든 가능한 수는 num의 자릿수에 따라 달라집니다. 예를 들어, num이 네 자릿수 (예: 1234, 3421 등)일 때, taken 또한 네 개의 비트 값을 가지며, 이에 대한 경우의 수는 2^4 = 16이 됩니다. 편의를 위해, int 형의 최대값의 자릿수인 열 네자리만큼의 저장공간을 미리 생성해두기로 합니다. 생성할 배열의 이름을 cache라고 하고 해당 배열의 크기는 2^14 = (1 << 14) = 16384가 됩니다. (실제코드 : int cache[1 << 14])

  위에서 설명한 cache와 taken을 통해 같은 숫자를 선택한 상황에서의 대한 경우의 수를 구하기 위한 중복계산을 없앨 수 있습니다. 그러나, 분해3의 문제에서는 num보다 작은 값들만 결과로 출력해야 한다는 조건이 있습니다. 따라서, 같은 숫자들을 선택했다 하더라도 해당 값이 num보다 크면 조건을 만족하는 수가 아니게 됩니다. 예를 들어, num = 2103 일때, 앞의 두 자리수가 12일 때는 뒤에 어떤 숫자가 나오더라도 항상 num보다 작지만, 21일 때는 뒤에 어떤 숫자가 나오더라도 항상 num과 같거나 크게 됩니다. 따라서, 매번 현재 값을 선택할 때마다 선택으로 인해 num보다 커지게 되는 값들은 배제해야 합니다. 예를 들어, num = 2103 일때, 첫번째 자리수를 2로 선택한다고 하면, num과 같기 때문에 아직 num보다 크다 작다를 확정할 수 없습니다. 다음으로, 두번째 자리수를 0으로 선택한다고 하면 2013, 2031 등의 값들은 항상 num보다 작다고 할 수 있습니다. 그러나 두번째 자리수가 3일 때, 2301, 2310과 같이 뒤에 어떤 값이 오더라도 항상 num보다 크게 되며 이는 결과로 출력하면 안되는 값들이 됩니다. 위와 같이, 어떤 숫자를 선택함으로써 다음에 선택될 값과 관련없이 항상 num보다 작다는 것을 알 때, 이를 표시해두어야 합니다. 그렇지 않으면, 이후의 값들을 검사하면서 해당 자리수의 값이 num의 선택할 자리수의 값보다 크다는 이유만으로 결과에서 배제 될 수 있기 때문입니다. 예를 들어, num = 2103이고 현재 20까지 선택이 되었을 때, 이후에 어떤 숫자가 나와도 항상 num보다 작다는 것을 알 수 있습니다. 그러나, 기존 알고리즘과 마찬가지로 num의 세번째 자리수 값인 0과 남은 선택 가능 숫자들 중 3을 비교 했을 때, 3이 더 크기 때문에 해당 경우를 결과에서 배제할 수 있습니다. 이러한 오류를 방지하기 위해 재귀 함수 price의 매개 변수에 idx와 taken과 더불어 bool isLess를 별도로 관리해야 합니다. 만약 현재까지 선택된 값이 num보다 항상 작다는 것을 보장할 수 있으면 isLess = true가 됩니다. 만약 isLess = true라면, 그 이후의 선택될 값들을 검사하는 과정에서 해당 자리수의 값이 num보다 크더라도 배제하지 않고 계속 재귀함수를 이어나가게 됩니다.

  isLess 변수와 더불어, cache 배열에도 별도의 추가공간을 설정해주어야 합니다. 기존 cache에는 선택된 값들만을 인덱스로 사용하여 저장된 값에 접근했습니다. 그러나, 이번에는 선택된 값들 + 그 값들이 num보다 작은지 여부를 인덱스로 하여 cache에 접근하도록 함으로써 서로 다르게 값을 관리할 수 있게 됩니다. 

(실제코드: int cache[1 << 14][2])

 isLess를 cache의 인덱스로 사용하여 만약 isLess = false라면 cache[][0]에 접근할 것이고, isLess=true라면 cache[][1]에 접근할 것 입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#define MAXNUMBER 14
 
vector<int> numVec;
vector<int> logVec;
vector<int> vec;
vector<bool> usedVec;
int cache[1 << MAXNUMBER][2];
 
int price(int idx, int taken, bool isLess){
    int size = vec.size();
    if (idx == size){
        return isLess?1:0;
    }
    int& cc = cache[taken][(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);
        bool newLess = isLess || vec[i] < numVec[idx];
        cc += price(idx + 1, newTaken,newLess);
        usedVec[i] = false;
        logVec.pop_back();
    }
    return cc;
}
 
void main(){
    long long num;
    cin >> num;
    cout << "입력:" << num << 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--;
    }
    int size = numVec.size();
    int nrNum = 1 << size;
    
    for (int i = 0; i < nrNum; i++){
        for (int j = 0; j < 2; j++){
            cache[i][j] = -1;
        }
    }
    int answer = price(0, 0, false);
    cout << "경우의수:" << answer << endl;
}

 만약 모든 자리수의 값을 모두 선택하였다면 (라인 16-18), 완성된 숫자에 대하여 isLess =true 일 경우, 해당 값은 num보다 작은 값이므로 결과에 포함하기 위해 1을 반환하고, isLess = false라면 num보다 크거나 같은 값이므로 결과에서 배제하기 위해 0을 반환합니다.

  초기에 cache의 각 원소 값들은 모두 -1로 초기화되어있습니다. 그리고 특정 값들을 선택한 상황에서 경우의 수를 계산하기 위해 해당 cache 값을 0으로 변경합니다. 그리고 모든 경우의 수들을 cache에 누적하는 방식입니다. 라인 20과 같이 만약 해당 현재 taken과 isLess값을 기반으로 cache의 값에 조회를 했을 때, 값이 -1이 아니라면 해당 값은 이미 계산이 완료가 된 값이므로 반복문에 진입하지 않고 해당 값을 반환합니다. 이는 동적계획법을 활용하여 불필요한 중복연산을 제거한 것입니다. price 함수는 주어진 num에 대해 모든 가능한 숫자들의 나열중에서 num보다 작은 값들의 수를 반환하는데요, 그 수는 cache[0][0]가 됩니다. 추가적으로 설명드리자면, cache[0][0]을 구하기 위해 cache[1][0] + cache[2][0] + cache[4][0] + cache[8][0] + ... 가 필요하며, cache[1][0]을 구하기 위해 cache[3][0] + cache[5][0] + cache[9][0] + ... 가 필요합니다. 또한, cache[2][0]을 구하기 위해 cache[3][0] + cache[6][0] + cache[10][0] + ... 가 필요한데, 여기서, cache[3][0]가 두번 계산되는 것을 알 수 있습니다. 이때 cache[3][0]은 미리 계산된 값을 보관하고 있으므로 바로 사용될 수 있는 것입니다.

num = 2031일때,

오름차순으로 정렬하면 digits = 0123

0123, 0132, 0213, 0231, 0312, 0321

1023, 1032, 1203, 1230, 1302, 1320

2013

이렇게 총 13가지의 경우가 num보다 작다고 할 수 있으며 정상적으로 결과가 출력된 것을 알 수 있습니다.