[백준] 1086번: 박성원

문제

https://www.acmicpc.net/problem/1086

설명

먼저, 러프하게 문제를 푸는 방법을 생각해보자. 주어진 수를 적절히 선택하여 순열을 만들었을 때, 이 순열이 $K$ 로 나누어 떨어지는 확률을 구해야 한다. 다만, 두 가지 큰 제약이 존재한다.

각각의 수의 길이는 최대 50이고, unsigned long long 으로도 커버하지 못하므로 string 으로 받아야 할 것이다. 또한 숫자들을 이어붙여도 가능한 표현 범위를 넘어가므로 실제 수를 만들어 나머지를 계산할 수 없다.
주어지는 수는 최대 15개인데, 모든 순열을 만들어 확인하는 것( $15!$ )은 주어진 시간 제한을 넘어간다.

모듈러 연산은 덧셈, 뺄셈, 곱셈에 대해 닫혀 있다. 두 수 $a$ , $b$ 를 이어붙인 수는 $a * 10^{len(b)} + b$ 이다. 이어붙인 수에 모듈러 연산을 하게 되면, $(a * 10^{len(b)} + b) \,mod\, k = (a\,mod\,k) * (10^{len(b)})\,mod\,k + b \,mod\, k$ 가 성립함을 알 수 있다. 여기서 우리가 각 단계에서 필요한 정보는 각각의 수를 모듈러 연산한 수, 10의 거듭제곱을 모듈러 연산한 수임을 알 수 있다.

주어진 수를 순열에 포함시키는 경우를 비트마스킹(mask)하고, 순열을 $K$ 로 나눈 나머지가 r 이 되는 경우의 수를 dp[mask][r] 로 정의한다. 이를 통해 $K$ 로 나누어 떨어지는 순열의 수를 구한 후, 분자와 분모의 최대공약수를 구해 나눠줌으로써 기약분수를 구한다.

코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// dp[mask][r] = x: mask에 포함된 수를 통해 순열을 만들었을 때, k로 나눈 나머지가 r이 되는 경우의 수는 x
long long dp[1 << 15][100];

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
	int n;
	cin >> n;

	vector<string> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	int k;
	cin >> k;

	// 10^l % k
	vector<int> pow_of_tens(51);
	pow_of_tens[0] = 1;
	for (int i = 1; i <= 50; i++) {
		pow_of_tens[i] = (pow_of_tens[i - 1] * 10) % k;
	}

	vector<int> len(n), modk(n); // len[i]: v[i]의 길이, modk[i]: v[i] % k
	for (int i = 0; i < n; i++) {
		len[i] = v[i].length();

		for (int j = 0; j < v[i].length(); j++) {
			modk[i] = (modk[i] * 10 + (v[i][j] - '0')) % k;
		}
	}

	dp[0][0] = 1;
    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int r = 0; r < k; r++) {
            if (dp[mask][r] == 0) continue;

            for (int i = 0; i < n; ++i) {
                // i번째 숫자를 순열에 포함시키지 않은 경우
                if (!(mask & (1 << i))) {
                    int nmask = mask | (1 << i); // 순열에 포함시킨다.

                    int nr = (r * pow_of_tens[len[i]] + modk[i]) % k;

                    dp[nmask][nr] += dp[mask][r];
                }
            }
        }
    }

    long long p = dp[(1 << n) - 1][0]; // 모든 숫자를 썼을 때 나머지가 0인 경우의 수

    if (p == 0) {
        cout << "0/1" << endl;
        return 0;
    }

    // q = n!
    long long q = 1;
    for (int i = 1; i <= n; ++i) {
        q *= i;
    }

    cout << p / gcd(p, q) << "/" << q / gcd(p, q);
}

dp[0][0] = 1;
for (int mask = 0; mask < (1 << n); mask++) {
    for (int r = 0; r < k; r++) {
        if (dp[mask][r] == 0) continue;

        for (int i = 0; i < n; i++) {
            // i번째 숫자를 순열에 포함시키지 않은 경우
            if (!(mask & (1 << i))) {
                int nmask = mask | (1 << i); // 순열에 포함시킨다.

                int nr = (r * pow_of_tens[len[i]] + modk[i]) % k;

                dp[nmask][nr] += dp[mask][r];
            }
        }
    }
}

dp[0][0] 은 아무 숫자를 순열에 포함시키지 않았고, 이를 $k$ 로 나누면 당연히 0이다. 이런 경우는 한 가지 존재하므로 1로 초기화한다.

첫 번째 for문에서 가능한 순열 조합을 순회한다. 두 번째 for문에서 현재 mask 에서 발생할 수 있는 모든 나머지 r 에 대해 확인한다. dp[mask][r] == 0 은 현재 mask와 r을 만족하는 순열의 수가 0이라는 것이고, 다음 단계로 넘어갈 수 없다. 따라서 이 경우 더 계산을 진행하지 않고 넘어간다.

세 번째 for문에서 i는 다음에 이어붙일 숫자의 인덱스이다. i번 째 숫자가 순열에 포함되지 않았다면 포함시키고(nmask), 포함하였을 때의 나머지(nr)를 계산한다.

시간복잡도

시간복잡도는 3중 for문에서 발생한다. 모든 비트마스크 상태를 확인하는 데 $O(2^N)$ , 모든 나머지 상태를 확인하는 데 $O(K)$ , 이어붙일 수를 선택하는 데 $O(N)$ 번의 연산을 수행한다. 따라서 총 시간복잡도는 $O(2^N\cdot K\cdot N)$ 이다.

공간복잡도

공간복잡도는 DP 배열에 의해 결정되고, $O(2^N\cdot K)$ 이다.