[BOJ] 백준 1086 - 박성원

문제 링크

www.acmicpc.net/problem/1086

1086번: 박성원

 

풀이

문제를 해결하기에 다음과 같은 어려움이 있습니다.

 

1) 모든 순열을 고려해봐야 하는데 $O(N!)$이라 경우의 수가 너무 많습니다.

2) 순열을 합친 큰 정수가 커도 너무 큽니다. 최대 750자리 수입니다.

 

수가 너무 큰데??

2번 문제부터 해결해봅시다.

 

사실 우리는 정확한 수를 알고 있을 필요가 없습니다. 결국 알고 싶은 사실은 어떤 수 $x$가 $k$로 나누어 떨어지는지입니다.

이를 백준 8111 - 0과 1 문제와 같은 방식으로 생각해볼 수 있습니다. 

모든 수를 $k$로 나눈 나머지만 보관하도록 합시다.

 

하지만 차이가 있습니다. 0과 1  문제에선 어떤 수 $x$에 10을 곱한 수의 나머지를 계산하니까 c++에서 지원하는 수 범위 내에서 연산을 할 수 있었는데, 이 문제에선 최대 50자리인 두 수를 이어 붙여야 합니다.

 

어떤 두 수를 $a, b$라 하고, 그 길이를 $l_a, l_b$라 합시다.

$a, b$를 이어 붙인 수 $x$를 다음과 같이 표현할 수 있습니다.

$$x = a\cdot10^{l_b} + b$$

여기서 $a\cdot10^{l_b}\text{ mod }k$를 구할 수 없는 게 문제입니다.

모듈러 연산은 덧셈, 뺄셈, 곱셈에 대해 닫혀있으므로 식을 다음과 같이 표현해봅시다.

$$a\cdot10^{l_b}\text{ mod }k = (a\text{ mod }k)(10^{l_b}\text{ mod }k)\text{ mod }k$$

 

$10^{l_b}\text{ mod }k$는 한 자리씩 늘려가며 50자리까지 결과를 전처리해둘 수 있고(line 43 ~ 46) , $a\text{ mod }k, b\text{ mod }k$ 또한 처음 입력받을 때 한 자리씩 계산하여 전처리해둘 수 있습니다(line 47 ~ 55).

 

이렇게 전처리 과정을 거치면 모든 수를 $k$ 미만의 수로 관리할 수 있게 됩니다.

 

 

모든 순열을 탐색할 필요가 없다

1번 문제를 해결해봅시다.

 

결론부터 말하면 비트 마스킹을 이용한 DP로 해결할 수 있습니다.

$D[s][i]$: 현재까지 집합 $s$에 포함된 수를 이용했고, 그렇게 만들어진 수가 $i$일 때, 남은 수들을 이용하여 만들 수 있는 $k$로 나누어 떨어지는 수들의 개수

 

백준 2098 - 외판원 순회 문제를 풀어보셨으면 쉽게 이해하실 수 있습니다.

$k \leq 100$이므로 어떤 순서로 순열을 만들든 간에 기껏해야 (집합의 수 * 100)가지 상태가 생깁니다. 따라서 메모이제이션을 이용하면 모든 순열을 탐색할 필요가 없어지게 됩니다.

 

정답 코드

#include <bits/stdc++.h>
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
#define mem(v, e) memset((v), (e), sizeof((v)))
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n, mod;
int tenPow[55];
string nums[22];
pii p[22];
ll d[1 << 15][111];

ll go(int s, int num) {
    if (s == (1 << n) - 1) return (num % mod == 0);

    ll &ret = d[s][num];
    if (ret != -1) return ret;
    ret = 0;
    for (int k = 0; k < n; k++) {
        if (s & (1 << k)) continue;
        auto[next, cnt] = p[k];
        ll nextNum = num * tenPow[cnt] + next;
        nextNum %= mod;
        ret += go(s | (1 << k), nextNum);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    ll all = 1;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        all *= (i + 1);
    }
    cin >> mod;
    tenPow[0] = 1 % mod;
    for (int i = 1; i < 55; i++) {
        tenPow[i] = (tenPow[i - 1] * 10) % mod;
    }
    for (int i = 0; i < n; i++) {
        reverse(all(nums[i]));
        p[i].sd = nums[i].size();
        for (int j = 0; j < nums[i].size(); j++) {
            p[i].ft += (nums[i][j] - '0') * tenPow[j] % mod;

        }
        p[i].ft %= mod;
    }
    mem(d, -1);
    ll cnt = go(0, 0);
    ll g = gcd(all, cnt);
    cout << cnt / g << "/" << all / g;
}