[백준 알고리즘] 1086번 박성원 c++

long long 변수형을 써야되는데서 삽질을 했다..

역시 변수의 최대범위는 잘 확인해야...

숫자들은 최대 길이가 50이상이므로 string 자료구조로 받아 처리해야 된다.

ten_mod_k에 1%k, 10%k, .. 10^50%k값을 구한다

mod_k에 각 원소의 %k 값을 구하고, dp값을채운다

dp[a][b]에서 a는 비트마스크로 해당위치의 원소가 쓰였는지 확인하고,

b는 0~k-1값으로, 비트마스크로 확인한 원소로 숫자를 만들었을때 나머지가 b인 개수이다.

ex) n = 3, [1, 2, 3] k=2

d[1][0]=0, d[1][1] = 1, d[2][0] = 1, d[2][1] = 0, d[4][0] = 0, d[4][1] = 1

 

ten_mod_k와 mod_k, d배열을 통해 0 ~ (1>>n) - 1

즉, n개의 비트마스크가 1일때까지// i for문

각 비트마스크를 확인해서 해당위치의 원소가 안쓰였다면 //j for문

0~k-1까지 d[i][m]을 탐색한다//m for문

a는 해당위치의 원소를 썼을때의 비트마스크(a= i | (1<<j))

b는 뒤에 원소를 추가했을 때 %k 값

d[a][b]에 d[i][m]을 더해준다.

 

%연산의 특징은  (x1*x2)%k = ((x1%k)*(x2%k))%k 이다.

따라서 m for문의 원소는 m*ten_mod_k[num_list[j].size()] + mod_k[j]로 구해질 수 있다. 

123456%k -> (1234*100)%k + 56%k -> ((1234%k * 100%k) + 56%k)%k

 

결과적으로 나눠떨어지는 값이 0인 개수는 d[(1<<n)-1][0]에 저장되고,

n!값인 total과 d[(1<<n)-1][0]인 possible을

최대공약수로 나누어 값을 출력하면 된다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
typedef long long ll;

ll d[1<<15][100];

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

int main(){
	int n, k;

	cin >> n;

	string num_list[n];
	int ten_mod_k[51], mod_k[n];

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

	cin >> k;

	ten_mod_k[0] = 1%k;

	for(int i=1; i<=50; i++){
		ten_mod_k[i] = (ten_mod_k[i-1] * 10) % k;
	}

	ll total = 1;

	for(int i=0; i<n; i++){
		int x = 0;
		total *= i+1;

		for(int j=0; j<num_list[i].size(); j++){
			x = x*10 + (num_list[i][j] - '0');
			x = x%k;
		}

		d[1<<i][x] = 1;
		mod_k[i] = x;
	}
	for(int i=0; i<(1<<n); i++){
		for(int j=0; j<n; j++){
			if((i &(1<<j)) == 0){
				int a = (i | (1<<j));
				for(int m=0; m<k; m++){
					int b = (m*ten_mod_k[num_list[j].size()]) + mod_k[j];
					b = b%k;

					d[a][b] += d[i][m];
				}
			}
		}
	}

	ll possible = d[(1<<n)-1][0];

	if(possible == 0){
		cout << "0/1" << endl;
	}
	else if(possible == total){
		cout << "1/1" << endl;
	}
	else{
		ll g = gcd(total, possible);
		cout << possible/g << "/" << total/g << endl;
	}

	return 0;
}