4. DP Technique - 웨브바짐 (zimbabwe) 문제

문제에서 이전 계란의 가격은 다음 세가지 조건을 만족해야한다.

1. 현재 계란 가격 e에 포함된 숫자들을 재배열한 결과여야 한다.

2. 현재 계란 가격 e보다 작아야 한다.

3. m으로 나누어 떨어져야 한다.

완전 탐색의 방법으로는 e의 숫자들을 재배열한 모든 가격을 만들어보고 그 중에서 e보다 작고 m으로 나누어 떨어지는 것들을 찾을 수 있다.

현재 계란 가격 e가 n자리 라고 할 때 전체 문제를 n조각으로 나누어 각 조각에서 가격의 한자리씩 정하도록 한다.

재귀함수는 지금까지 만든 가격의 일부분과 각 자릿수의 사용여부를 입력으로 받아 처리한다.

그런데 만약 예제 입력의 422 같은 경우는 동일한 숫자가 2개가 되어 완전탐색으로 구현시 중복된 경우를 셀 수 있게 된다.

중복된 가격을 만들지 않기 위해서 가격의 각 위치의 숫자들을 정렬하여 digits 라는 문자열에 저장하고 항상 앞에 오는 것부터 선택하도록 한다.

이를 구현하기 위해 현재 선택할 숫자는 digist의 첫번째 원소이거나, digit의 앞자리와 다른 숫자이거나, digit의 앞자리가 이미 선택된 경우여야 한다.

// 웨브바짐 문제의 답을 모두 찾는 완전 탐색 알고리즘

string e, digits;

int n, m;

void generate(string price, bool taken[15]){

// base case : 가격을 n자리 까지 모두 만들었으면 e보다 작고 m으로 나누어 떨어지는지 확인하고 출력

if( price.size() == n) {

if( price < e && atoi(price.c_str()) % m == 0 ) 

cout << price << endl;

return;

}

// 0번째 자리부터 n-1번째 자리까지 숫자를 선택하여 정한다.

for(int i = 0; i < n; i++){

if( !taken[i] && ( i ==0 || digits[i-1] != digits[i] || taken[i-1])){

taken[i] = true;

generate(price + digits[i], taken);

taken[i] = false;

}

}

}

위 코드에서 e와 digits를 정수형 변수가 아닌 문자열에 저장하는 것을 볼 수 있다.

자릿수 단위로 숫자를 다뤄야 하기 때문에 문자열로 다루는 것이 더 편하기 때문이다.

문자열 형태로 저장하더라도 price와 e의 자릿수가 같기 때문에 <, > 연산자를 이용해 대소 비교를 할 수 있다.

그런데 위의 코드는 메모이제이션을 적용하지 않아서 비효율적이고 속도가 느리다.

메모이제이션을 위해 불린 값 배열인 taken은 정수형으로 나타내고, price는 필요한 정보만을 남겨 최소화 해야한다.

그러기 위해서는 price가 쓰이는 용도를 파악해야 한다.

일단 price는 가격이 n자리까지 모두 완성되었는지 판단하기 위해 쓰이고,

전체 가격이 만들어졌을 때 e보다 작은지 판단하기 위해 쓰이고 m으로 나누어 떨어지는지 확인하기 위해 쓰인다.

먼저, 만든 가격이 e보다 작은지 확인하는 방법을 생각해보자.

e와 e의 숫자들을 재조합해서 만든 price의 자릿수가 같기 때문에, 앞자리에서 부터 비교하여 대소를 비교할 수 있다.

e의 첫번째 자리 숫자가 price의 첫번째 자리 숫자보다 크면 price의 두번째 자리부터는 어떤 조합이 와도 e보다 작기 때문에 신경쓰지 않아도 된다.

그러나 두 첫번째 자리 숫자가 같다면 두번째 자리 숫자는 e의 두번째 자리 숫자보다 작거나 같아야 할 것이다.

즉, 함수에 현재 만든 자릿수까지 비교하여 price가 e보다 작은지를 나타내는 입력값 less를 전달해 주어야한다.

less가 true이면 현재까지 만든 price의 앞부분이 e의 앞부분보다 작다는 것을 의미한다.

이때는 뒤에 어떤 숫자의 조합이 와도 상관없다.

less가 false이면 price가 e의 앞부분과 일치한다는 것을 의미한다.

이때는 뒤에 e의 해당 자릿수보다 큰 수를 선택하면 안된다.

그 다음으로 m의 배수가 맞는지 확인하는 방법을 생각해보자.

우리는 최소한의 정보만으로 m의 배수인지를 판단하기 위해 나머지 연산의 분배 법칙을 이용하도록 한다.

  

위의 그림에서 보듯이 7284를 6으로 나누는 과정과 13284를 6으로 나누는 과정이 284 이후부터 동일한 것을 알 수 있다.

나눗셈을 할 때 앞의 수를 나누고 남은 나머지와 뒤의 수에서 한자리씩 내려서 나누기 때문이다.

즉, 앞의 7과 13을 6으로 나눈 나머지가 1로 동일하여 뒤에 오는 284를 나누는 과정이 동일해지는 것이다.

그러면 우리는 재귀함수에 앞에서 만든 price를 m으로 나눈 나머지만 전달하면 그 나머지에 현재 선택하게된 숫자를 붙여서 또 나머지를 계산할 수 있다.

위의 아이디어를 적용하여 다음과 같이 코드를 구현할 수 있다.

현재 만드는 price의 현재 위치를 알기 위해서 현재 만들 숫자의 위치를 나타내는 index를 함수의 입력으로 받는 것도 확인할 수 있다.

// 웨브바짐 문제를 해결하는 다이나믹 프로그래밍 알고리즘

int n,m;

string e, digits;

const int MOD = 1000000007;

int cache[1>>14][20][2];  // e는 최대 10^14까지 가능 - > 15자리까지 가능

int price(int index, int taken, int mod, int less){

// base case : n자리 까지 가격을 완성시켰으면 e보다 작고 m으로 나누어떨어지는지 확인 후 결과값 리턴

if( index == n){

if( mod == 0 && less == 1) return 1;

else return 0;

}

// 메모이제이션

int& ret = cache[taken][mod][less];

if( ret != -1 ) return ret;

// taken의 인덱스를 처음부터 끝까지 순회하면서 price에 현재 넣을 숫자를 선택한다.

ret = 0;

for(int next = 0; next < n; next++){

if( taken & (1 << next) == 0){

// 만약 현재까지 만든 가격의 앞자리가 e의 앞자리와 같다면(less == 0) 

// 지금 선택할 숫자는 e의 해당자리 숫자보다 크면 안된다.(같거나 작아야함)

if( !less && e[index] < digits[next]) continue;

// e에 같은 숫자가 있을 경우 항상 digits의 앞의 원소부터 선택한다.

if( next > 0 && digits[next-1] == digits[next] && !( taken & (1<< (next-1))) ) continue;

int nextTaken = taken + (1 << next);

int nextMod = ( mod * 10 + digits[next] - '0') % m;

int nextLess = less || (e[index] > digits[next]);

ret += price(index+1, nextTaken, nextMod, nextLess);

ret %= MOD;

}

}

return ret;

}

index는 taken에 포함된 true수와 같기 때문에 중복된 정보이므로 메모이제이션에 사용하지 않는다.