[Baekjoon,1086] 박성원

이 문제는 주어진 숫자들로 조합을 하여 주어진 $K$로 나누어 질 수 있는 조합의 개수를 찾아 해결하는 문제이다. 이는 모든 조합을 탐색하며 해당 조합의 숫자가 $K$로 나누어 떨어지는지 찾으면 된다. 이때 주어지는 숫자의 개수가 15개이므로 비트 마스크를 이용하여 해당 숫자에 대해 방문 여부를 체크하면 메모이제이션이 가능하다.

하지만 문제가 되는 것은 아래의 두 가지이다.

1. 숫자의 길이가 50이나 되는데 어떻게 나머지를 구하지?
2. 숫자를 조합하여 탐색하다 보면 숫자의 길이가 엄청 길어지는데 이를 어떻게 처리하지?

큰 숫자의 나머지를 구하는 방법

1번을 해결하는 방법은 실제로 나머지 연산하는 과정을 따라 가 보면 알 수 있다. 예를 들어 $54321$을 $16$으로 나눈 나머지를 구하는 과정을 살펴보자.

$ \begin{array}{*3r @{\hskip5pt}c@{\hskip5pt} *5r} & & 0 & 3 & 3 & 9 & 5 \\ \hline 16 & \big) & 5 & 4 & 3 & 2 & 1 \\
& & 0 & & & & \\ \hline & & 5 & 4 & & & \\
& & 4 & 8 & & & \\ \hline & & & 6 & 3 & & \\
& & & 4 & 8 & & \\ \hline & & & 1 & 5 & 2 & \\
& & & 1 & 4 & 4 & \\ \hline & & & & & 8 & 1 \\
& & & & & 8 & 0 \\ \hline & & & & & & 1 \\
\end{array} $

1. 처음에는 5의 자리 수 $5$가 $16$으로 나눠지는 지 확인할 것이다. 하지만 나눠지지 않는다. 이는 $5mod16=5$로 나머지가 $5$가 나온다.
2. 주어진 나머지 $5$를 다음 4번째 자릿수인 $4$의 앞으로 두어 합친다. 이 다음에 합쳐진 $54$를 $16$으로 다시 나눈 나머지를 구한다. 이는 $6$이다.
3. 다시 주어진 $6$을 3번째 자릿수인 $3$의 앞으로 두어 합친다. 합쳐진 $63$을 $16$으로 나눈다. 이는 $15$이다.
4. 계속 반복한다. 최종적으로 $81$을 $16$으로 나눈 나머지 $1$을 얻을 수 있다.

이러한 방법으로 현재까지 만들어진 수열의 뒷 부분에 다음 수열을 뒤에 이어 나머지 연산을 진행할 수 있다. 즉, 매개 변수로 나머지만 넘기면 된다. 하지만 매번 다음 나머지를 찾기에는 너무 오랜 시간이 걸려 아래와 같은 구현은 시간초과를 받는다.

int getNextMod(string num, int hereMod)
{
    int mod=(hereMod*10+num[0])%K;
    for(int i=1;i<num.size();++i)
        mod=(mod*10+int(num[i]-'0'))%K;
    return mod;
}

// 느려 통과할 수 없는 코드이다. 
long long try1(int mod, int visited)
{
    // 순열이 완성된 경우 
    if(visited==((1<<N)-1))
        return mod==0;

    long long& ret=cache[mod][visited];
    if(ret!=-1)
        return ret;
    ret=0;
    // 모든 조합을 만들어 본다.
    for(int i=0;i<N;++i)
        if(!(visited&(1<<i)))
        {
            int nextMod=getNextMod(perms[i],mod);
            ret+=try1(nextMod,visited|(1<<i));
        }
    return ret;
}

---

미리 계산하자

그렇다면 해당 값들을 미리 계산해 두면 되지 않을까? 위 코드에서 알 수 있는 다음 나머지에 대한 식은 아래와 같다.

$ nextMod=(hereMod*10^{perms[i].size()}+perms[i])modK $

이는 기존 나머지 뒤에 새로운 수열을 이어서 나머지를 구하는 것이다. 이는 모듈러 연산의 분배법칙을 이용하여 아래와 같이 변형이 가능하다.

$ nextMod=(hereMod * 10^{perms[i].size( ) } modK + perms[i]modK) modK $

이때 $ pow10[i]=10^{perms[i].size( ) } modK, \ \ mods[i]=perms[i]modK $ 라고 정의하여 두 배열을 미리 계산하면 빠른 속도로 해결 가능하다.

int moduler(string num)
{
    int mod=0;
    for(int i=0;i<num.size();++i)
        mod=(mod*10+int(num[i]-'0'))%K;
    return mod;
}

void preCacl()
{
    memset(cache,-1,sizeof(cache));
    for(int i=0;i<N;++i)
        mods[i]=moduler(perms[i]);
    pow10[0]=1%K;
    for(int i=1;i<51;++i)
        pow10[i]=(pow10[i-1]*10)%K;
}

---

구현

그 후 유클리드 호제법을 이용하여 최대 공약수로 분모, 분자를 나눠 결과를 출력하면 된다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

const int MAX_N=15;
const int MAX_K=101;

int N,K;
vector<string> perms;
// mods[i] = perms[i] % K, pow10[i] = 10^i % K
int mods[MAX_N], pow10[51];
// [뒤의 3자리 수열][방문한 곳]
long long cache[MAX_K][1<<MAX_N+1];

int moduler(string num)
{
    int mod=0;
    for(int i=0;i<num.size();++i)
        mod=(mod*10+int(num[i]-'0'))%K;
    return mod;
}

void preCacl()
{
    memset(cache,-1,sizeof(cache));
    for(int i=0;i<N;++i)
        mods[i]=moduler(perms[i]);
    pow10[0]=1%K;
    for(int i=1;i<51;++i)
        pow10[i]=(pow10[i-1]*10)%K;
}

long long solve(int mod, int visited)
{
    // 순열이 완성된 경우 
    if(visited==((1<<N)-1))
        return mod==0;

    long long& ret=cache[mod][visited];
    if(ret!=-1)
        return ret;
    ret=0;
    // 모든 조합을 만들어 본다.
    for(int i=0;i<N;++i)
        if(!(visited&(1<<i)))
        {
            int nextMod=(mod*pow10[perms[i].size()]+mods[i])%K;
            ret+=solve(nextMod,visited|(1<<i));
        }
    return ret;
}

// n,m에 대한 최대 공배수를 구한다. 
long long gcd(long long n, long long m)
{
    if(m==0)
        return n;
    return gcd(m,n%m);
}

int main()
{
    cin>>N;
    perms=vector<string>(N);
    for(int i=0;i<N;++i)
        cin>>perms[i];
    cin>>K;

    preCacl();
    
    long long p=solve(0,0);
    long long q=1;
    for(int i=2;i<=N;++i)
        q*=i;

    long long div=gcd(p,q);

    if(p==0)
        cout<<"0/1"<<endl;
    else if(p==q)
        cout<<"1/1"<<endl;
    else
        cout<<p/div<<'/'<<q/div<<endl;

    return 0;
}

---

회고

초기에 $1234$를 $12$로 나눈 나머지와 앞에 숫자를 붙힌 $81234$를 $12$로 나눈 나머지를 같다고 생각했었다. 지금 보면 절대 같을 수 없는데 말이다.