BOJ 1086 - 박성원 (dp, bit set)

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

비트셋을 이용한 어려운 dp

 

<문제설명>

수가 최대 15개 주어질 때, 이 수를 모두 사용한 순열을 순서대로 이어붙인 숫자 중 k(최대100)로 나눠떨어지는 것의 개수를 이용해서 확률을 구하라.

 

 

<풀이>

dp[i][j] : i(집합) 골랐을 때 나머지가 j인 것의 수. 초기값은 0으로 한다. (단, dp[0][0] = 1)

최종적으로 dp[(1<<n)-1][0] (모두골랐을 때 나머지가 0인 것의 수)를 분자로 출력하면 된다.

분모는 당연히 전체 순열의 수인 n!이다.

 

현재 집합이 i이고 나머지가 j일 때, i에 속하지 않은 l번 수를 뒤에 이어붙였을 때 나머지를 next라고 하면

d[i | (1<<l)][next] += dp[i][j]

 

next = (새로만들어진 수) % k

 = (원래 수 * pow( 10, len(l번째 수) ) + l번째 수) % k 

 = [ (원래 수 * pow( 10, len(l번째 수) ) ) % k  + l번째 수 % k ] % k

 = [ (원래 수 % k  * pow( 10, len(l번째 수) ) % k ) %k + l번째 수 % k ] % k

 = [ (j * pow( 10, len(l번째 수) ) % k ) % k +    l번째 수 % k ] % k

 

여기서 l번째 수 = a(l)   /// l번째 수의 길이 = len(l)   ///  10의 t승의 모듈러 k 값 = ten(t)로 전처리를 해둔다면,

 

next = [ (j*ten(len(l))) % k + a(l)%k ] % k

라고 할 수 있다...

 

새롭게 만들어진 수의 모듈러 k값은, 원래 수의 모듈러 k값인 j와 새롭게 추가되는 수의 정보만 있으면 만들 수 있다.

 

 

<코드>

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
ll d[1 << 15][101];
ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

int main() {
	int n; cin >> n;
	vector<string> num(n);
	vector<int> a(n);   //i번째 수의 k모듈러값
	vector<int> len(n); //i번째 수의 길이
	for (int i = 0; i < n; i++) {
		cin >> num[i];
		len[i] = num[i].size();
	}
	int k; cin >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < len[i]; j++) {
			a[i] = a[i] * 10 + (num[i][j] - '0');
			a[i] %= k;
		}
	}
	vector<int> ten(51);  //10의 i승의 k 모듈러값
	ten[0] = 1;
	for (int i = 1; i <= 50; i++) {
		ten[i] = ten[i - 1] * 10;
		ten[i] %= k;
	}
	d[0][0] = 1;
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 0; j < k; j++) {
			for (int l = 0; l < n; l++) {
				if ((i & (1 << l)) == 0) {
					int next = j * ten[len[l]];
					next %= k;
					next += a[l];
					next %= k;
					d[i | (1 << l)][next] += d[i][j];
				}
			}
		}
	}
	ll t1 = d[(1 << n) - 1][0];
	ll t2 = 1;
	for (ll i = 2; i <= n; i++) t2 *= i;
	ll g = gcd(t1, t2);
	t1 /= g;
	t2 /= g;
	cout << t1 << '/' << t2 << '\n';
}

 

<생각>

dp를 갱신하는 for문의 제일 바깥이 집합을 의미하는 i이다.

 

i = 0010 일때 L==0 을 넣는 것과

i = 0001 일때 L==1 을 넣는 것을 모두 고려했기 때문에 이 알고리즘은 완전하다고 할 수 있겠다.

(set1 < set2 인 모든 set1과 set2에 대해 set1이 set2보다 먼저 처리된다.)