[동적 계획법][비트 마스크][시간 초과] ZIMBABWE 웨브바짐

1. 완전 탐색

 

원래 가격은 다음에 해당해야한다

1. 바뀐 가격의 숫자들로만 이루어져있다.

2. 바뀐 가격보다 싸야한다

3. m의 배수야 한다.

 

다음은 이런 정보들을 통하여 완전 탐색하는 코드이다.

 

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
 
using namespace std;
//current p: e
// before p = m*r
// perm
string board;
int cnt[10];
 
int m=0;
 
void inputE()
{
    board = "";
    char tmp;
    getchar();
    for(;((tmp = getchar()) != '\n' )&& (tmp != ' ');)
    {
        board += tmp;
        cnt[tmp-'0']++;
    }
}
//modulo(m. 0, 0)
int modulo(int mod, int l, int remain, string &before)
{
    if(l == before.size()) return remain;
    modulo(mod, l +1, (remain*10 + (before[l] - '0'))%mod, before); 
}
 
// len == 0
int count(int len, int caution, string before)
{
    int ret = 0;
    if(len == board.size())
    {
        if(modulo(m, 0, 0, before) == 0)
            return 1;
   }
    
    for(int i = 0; i < 10; i++)
    {
        if(cnt[i] == 0) continue;
 
        int bNum = board[len] - '0';
        
        if((bNum < i && caution == len )|| (bNum == i && caution == len && len + 1== board.size()))
            break;
        
        if(bNum == i) caution++;
 
        cnt[i]--;
        ret = (ret + count(len + 1, caution, before + to_string(i)))%1000000007;
        cnt[i]++;
        if(bNum == i) caution--;
    }
    return ret;
}
int main()
{
    int testCase = 0;
 
    cin>>testCase;
 
    for (int i = 0; i < testCase; i++)
    {
        memset(cnt, 0, sizeof cnt);
 
        inputE();
        cin>>m;
        string tmp = "";
        cout<<count(0, 0, tmp)<<"\n";
    }
}

 

2. 동적 계획법을 사용하려면..

 

다음과 같은 정보가 필요하다.

1. 사용한 원소들의 정보

2. 이 때 까지 만든 수를 m으로 나눈 나머지

3. 이 때 까지 만든 수가 주의를 받은 횟수 -> 1과 0으로 나타낼 수 있음.

   (caution과 len이 같으면 len길이 만큼 같다, 즉 다음 추가되는 수가 더 클 경우 답이 생성되지 않음)

 

여기서 중요한점이

1번을 메모이제이션을 하는 것이다.

이것을 표현하려면 

따로 배열이나 문자열을 정수로 나타내는 함수가 필요하거나

비트마스크를 이용해야한다.

 

 

ZIMBABWE