[PS] 박성원 / C++ (백준 1086번)

 

 

비트마스킹을 활용한 dp 문제, 근데 이제 큰 수 % k를 곁들인 ..

 

시행 착오

 vector<pair<int, int> > dp[][]로 선언을 하여 dp[i][j] = i개의 원소를 합쳤을 때, 마지막 원소에 j번째 원소를 삽입한 pair(first = 지금까지 삽입한 원소들의 비트마스킹, second = k로 나눈 나머지)를 삽입하는 것으로 점화식을 짰다.

이 후에 말도 안 되는 메모리 초과를 보여주며 전처리 및 메모리도 줄인 후 진행했는데 여전히 답이 안 보였다.

 

해결 방안

갈아엎었다. 점화식부터 다시 구상하니 dp[i][j] = 지금까지 사용한 원소를 마스킹한 값이 i, 나머지가 j인 수열의 갯수 로 풀 수 있었다.

1. 전처리 및 dp에 각각 하나씩 사용한 경우의 수 저장
   1. ten_mod에 10^l 들을 k로 나눈 나머지를 모두 구해놓는다. 이때, 0<= l <= 750 (최대 n 크기 * 각 수의 최대 길이)
   2. element_mod엔 입력 받은 값들을 k로 나눈 나머지를 ten_mod를 이용해 구해놓는다. (mod_ 함수)
   3. dp[1<<i][element[i]를 나눈 나머지]에 1 저장 (digit[i][j] = dp[i][j]의 지금까지 자릿수)
2. 나머지 연산은 분배법칙이 성립하는 성질을 이용해 dp를 끝(1<<n - 1)까지 구한다.
3. dp[(1<<n)-1][0] 값과 factorial(n) 값의 최대 공약수를 구해서 문제 조건에 맞게 출력

 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
ll mod_(string str);
ll gcd(ll a, ll b);

int n, k;
ll ten_mod[751], element_mod[16];
string element[16];
ll dp[39993][101], digit[39993][101];

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) cin >> element[i];
	scanf("%d", &k);

	ll temp = 1;
	for (int i = 0; i < 751; i++) {
		ten_mod[i] = temp % k;
		temp = temp * 10 % k;
	}

	for (int i = 0; i < n; i++) {
		ll mod_val = mod_(element[i]);
		dp[1 << i][mod_val] = 1;
		digit[1 << i][mod_val] = element[i].size();
		element_mod[i] = mod_val;
	}

	for (int mask = 1; mask < (1 << n); mask++) {
		for (int i = 0; i < k; i++) {
			if (dp[mask][i]) {
				for (int j = 0; j < n; j++) {
					ll new_mask = mask | (1 << j), mod;
					if (new_mask == mask)continue;
					mod = (i + (element_mod[j] * ten_mod[digit[mask][i]]) % k) % k;
					dp[new_mask][mod] += dp[mask][i];
					digit[new_mask][mod] = digit[mask][i] + element[j].size();
				}
			}
		}
	}

	ll numerator = dp[(1 << n) - 1][0], denominator = 1;
	for (int i = 1; i <= n; i++) denominator *= i;
	if (numerator == 0) {
		printf("0/1\n");
		return 0;
	}
	ll gcd_ = gcd(denominator, numerator);
	printf("%lld/%lld\n", numerator / gcd_, denominator / gcd_);
	return 0;
}

ll mod_(string str) {
	ll hap = 0;
	for (int i = 0; i < str.size(); i++) {
		hap += (str[i] - '0') * ten_mod[str.size() - i - 1];
		hap %= k;
	}
	return hap;
}

ll gcd(ll a, ll b) {
	while (b != 0) {
		ll temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}