algospot ZIMBABWE

문제 링크입니다: https://algospot.com/judge/problem/read/ZIMBABWE

이 문제도 비트마스크를 사용했습니다.

하지만 이 문제는 비트마스크보다는 가격이 아닌 가격의 나머지만을 전달하더라도 M의 배수 여부를 판별할 수 있다는 것이 제일 중요했던 것 같습니다.

그리고 중복된 숫자를 세지 않는다는 것 또한 중요합니다!

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <cstring> //memset

#include <bitset>

using namespace std;

 

//digits: egg의 자릿수들을 정렬한 것

string egg, digits;

int N, M; //N은 egg의 자릿수, egg는 M으로 나누어 떨어져야한다

const int MOD = 1000000007;

//자릿수가 최대 14자리이므로 1<<14, M<=20, 그리고 egg보다 작은지 여부

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

 

/*

//egg의 자릿수로 만들 수 있는 숫자들을 모두 출력

//price:지금까지 만든 가격

//taken:각 자릿수의 사용 여부

void generate(string price, bool taken[15]) //가능한 가격을 모두 구하는 함수(완전 탐색)

{

        //기저 사례

        if (price.size() == N)

        {

               if (price < egg)

                       cout << price << endl;

               return;

        }

        for (int i = 0; i < N; i++)

        {

               //중복을 방지하기 위해 egg의 각 자릿수를 정렬해서 digits에 저장한 뒤

               //이번에 사용할 자릿수 바로 앞자리가 없거나

               //이번 자릿수랑 다르거나, 이미 사용된 경우만 사용하도록

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

               {

                       taken[i] = true;

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

                       taken[i] = false;

               }

        }

}

*/

 

//과거 가격을 앞 자리부터 채워나가고 있다

//index:이번에 채울 자리의 인덱스

//taken:지금까지 사용한 자릿수들의 집합

//remainder: 지금까지 만든 가격의 M에 대한 나머지

//less: 지금까지 만든 가격이 이미 egg보다 작으면 1, 아니면 0

long long price(int index, int taken, int remainder, int less)

{

        //기저 사례

        if (index == N)

               return (less && remainder==0) ? 1 : 0;

        //메모이제이션

        int &result = cache[taken][remainder][less];

        if (result != -1)

               return result;

        result = 0;

        for (int next = 0; next < N; next++)

               if ((taken & (1 << next)) == 0) //next번째 숫자를 사용한적이 없다면

               {

                       //과거 가격은 새 가격보다 항상 작아야만 한다

                       if (!less && egg[index] < digits[next])

                              continue;

                       //같은 숫자는 한번만 선택

                       if (next > 0 && digits[next - 1] == digits[next] && (taken & (1 << (next - 1))) == 0) //next-1번째 숫자를 이미 사용했고 연속해서 같은 숫자이면

                              continue;

                       int nextTaken = taken | (1 << next); //next번째 숫자를 사용했다고 표기

                       //나머지가 같을 경우 앞에 어떤 수가 왔는지는 중요하지 않다. 나머지만 전달해도 계란 가격이 m의 배수인지 알 수 있다

                       int nextRemainder = (remainder * 10 + digits[next] - '0') % M; //다음 나머지

                       int nextLess = less || egg[index] > digits[next]; //작은 숫자 여부 확인

                       result += price(index + 1, nextTaken, nextRemainder, nextLess);

                       result %= MOD;

               }

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 0 || test_case>50)

               exit(-1);

 

        for (int i = 0; i < test_case; i++)

        {

               N = 0;

               vector<long long> candidate;

               memset(cache, -1, sizeof(cache));

               cin >> egg >> M;

               long long num = atoll(egg.c_str());

               candidate.clear();

               while (num > 0)

               {

                       candidate.push_back(num % 10);

                       num /= 10;

                       N++;

               }

               sort(candidate.begin(), candidate.end());

               for (int j = 0; j < N; j++)

                       digits += candidate[j]+'0';

               cout << price(0, 0, 0, 0) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략