[BOJ/백준] 1086번. 박성원 - C++[cpp]

문제

 

접근

만약 Bruete Force한 접근 방식으로 모든 경우를 다 구한다고 하면 O(n!)로 주어진 시간 내에 해결이 불가능하다.

어떻게 접근해야 할 지 잘 모르겠지만 분명 매 케이스마다 나머지를 하고 있으면 매우 많은 연산 시간이 필요하다는 것 정도는 알 수 있다. 

(문자열의 최대 길이가 50이기 때문에 특정 상태에서 나머지를 구할 때 해당 문자열 처음부터 끝까지 나머지를 계산하는 것 또한 매우 비효율적이다.)

 

따라서 먼저, 각 문자열의 수를 k로 나눈 나머지를 미리 기록해두자

int cachestr[16];

// 주어진 문자열과 제수(divisor)를 입력받아 나머지를 반환해주는 함수
int mod(const string &s, const int divisor) {
    int result = 0;
    for (int i = 0; i < s.length(); i++) {
        result *= 10;
        result += s[i] - '0';
        result %= divisor;
    }
    return result;
}

// 메인 함수에서
for (int i = 0; i < n; i++) cachestr[i] = mod(arr[i], k);

 

또 반복되서 계산되는 부분이 있는지 생각해보자.

 

특정 수 뒤에 새로운 수가 붙는다고 했을 때, 기존 수의 나머지 값을 알고 있으면 새로 이어진 수의 나머지 값 또한 빠르게 구할 수 있다.

또한, 모든 수는 a * 10^i + b * 10^(i - 1)....형태로 나타낼 수 있다.

==> 문자열의 최대 길이가 50이기 때문에 i가 0부터 50일 때 까지 나눗셈의 나머지 값을 미리 기록해두자.

 

(a × b) % k = [(a % k) × (b % k)] % k 라는 사실로부터, rcache[i] = (rcache[i - 1] * 10) % k라는 사실을 알 수 있다.

int rcache[51];

int main(void) {
	// 중략
    
    rcache[0] = 1;
    for (int i = 1; i < 51; i++) rcache[i] = (rcache[i - 1] * 10) % k;
    
    // ~~~
}

 

숫자를 결합시킬 때 새로운 나머지를 구하는 과정에서 이 rcache 배열을 이용하면 빠르게 구할 수 있다.

 

이제 위에서 봤던 원리를 이용해서 문제 풀이를 완성해보자.

 

이 문제에서 우리가 구해야 하는 것은 k로 나눠 떨어지는 순열의 수 이다. 문자열 N개를 모두 순서대로 나열한다면 TLE가 발생한다.

하지만 우리가 위에서 계산했던 방식을 잘 살펴보면 순열의 순서를 신경쓰지 않고도 원하는 값을 구할 수 있다는 사실을 캐치할 수 있다.

rcache를 구할 때 새로운 수를 붙여가면서 나머지를 기록했다. 이때는 10의 지수승 마다 나머지를 기록해뒀다.

 

만약 10이 아니라 숫자가 붙는다면? ==> 이것 또한 기록해둘 수 있다.

현재 포함되어 있는 문자열의 상태를 비트마스킹을 이용해서 나타내고, 새로운 숫자가 붙어 새로운 문자열을 구성할 때 기존의 데이터를 이용하면 새로운 숫자가 구성됬을 때 빠르게 나머지를 구할 수 있다.

 

for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) {
                int nextMask = mask | (1 << i);
                for (int j = 0; j < k; j++) {
                    int nextK = ((j * rcache[arr[i].length()]) % k + cachestr[i]) % k;
                    dp[nextMask][nextK] += dp[mask][j];
                }
            }
        }
    }

 

현재 집합 상태에서 새로운 수가 추가되었을 때 나머지를 기록해나가는 것이다.

nextK는 새로운 수가 추가되었을 때 k로 나눈 나머지를 의미하고 우리가 위에서 rcache를 구하는 방식과 동일하게 구할 수 있다.

그리고 dp[다음 상태][nextK] 에 현재 상태에 해당하는 수의 개수를 더해준다.

 

최종적으로 dp[111111...][0]이 우리가 구하고자 하는 k로 나눠 떨어지는 순열의 개수가 된다.

 

기약분수를 출력하기 위해서 최대공약수를 <numeric> 헤더 파일에 존재하는 gcd함수를 이용해 구한 뒤 분모 분자에 나눠주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

string arr[16];
int n, k;
long long dp[(1 << 16)][101]; // state, 나머지 r
int rcache[51];
int cachestr[16];

int mod(const string &s, const int divisor) {
    int result = 0;
    for (int i = 0; i < s.length(); i++) {
        result *= 10;
        result += s[i] - '0';
        result %= divisor;
    }
    return result;
}

long long factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

int main(void) {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    cin >> k;
    dp[0][0] = 1;
    rcache[0] = 1;
    for (int i = 1; i < 51; i++) rcache[i] = (rcache[i - 1] * 10) % k;
    for (int i = 0; i < n; i++) cachestr[i] = mod(arr[i], k);

    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) {
                int nextMask = mask | (1 << i);
                for (int j = 0; j < k; j++) {
                    int nextK = ((j * rcache[arr[i].length()]) % k + cachestr[i]) % k;
                    dp[nextMask][nextK] += dp[mask][j];
                }
            }
        }
    }
    auto divisor = factorial(n);
    auto dividened = dp[(1 << n) - 1][0];

    long long GCD = gcd(dividened, divisor);

    cout << dividened / GCD << "/" << divisor / GCD;
}