<백준 알고리즘> 비트마스킹 DP 1086번

백준 1086번

접근 방법

1. 숫자가 길기 때문에 직접 연산할 수는 없고 모든 순열에 관하여 계산해야 하므로 O(N!)가 걸리기에 다 구하는 방법말고 다른 방법으로 접근해야 했다.

2. 비트마스킹을 이용하여 순열을 표시하면 좋을 것 같다는 생각이 들었다. 추가로 N개의 수로 만든 수의 나머지가 0으로 나오는지 알기위해서 수를 조합해 갈 때 차례차례 나머지를 구하고 다음 수에 붙혀서 또 나머지를 구하고 이런 식으로 할 필요가 있다고 생각하여 DP로 접근해야겠다고 생각했다.

3. K가 100까지이므로 각 순열의 나머지를 구할때 100까지의 수를 담는 배열로
   DP[1 << 16][101]을 만들었다.
   만약 4개의 원소가 집합에 있을 경우 1000, 0100, 0010, 0001에서 나오는 나머지의 개수 1100, 1010,1001, 0110, 0101, 0011의 두 수를 선택했을 때 나오는 나머지의 개수 이런식으로 차례차례 더해가야 한다.

4. 이를 구현하기 위해 처음엔 DFS를 사용하여 자리 수 마다 돌고 와서 DP를 하려했는데 이러면 모든 경우를 구하는 것과 다를 바가 없기에 시간초과가 났다.

5. 그래서 1 << 15까지의 경우에 대하여 나올 수 있는 나머지와 만들 수 있는 조합을 반복문으로 구현해야 했다. 예를 들어 순열(P)가 1인 경우에 0001이라 할때 다음 순열에 대하여 구하였다. 0011, 0101, 1001 등으로 다음에 P가 2일 경우엔 0111, 1011, 1101으로 다음 순열에 대하여 구하는 방식으로 구현하였다.

+)추가로 배열에 있는 수를 그대로 쓰지 않고 미리 나머지를 구해놓았다.

몰랐던 것

나머지 연산의 속성을 활용하여 10의 제곱에 대한 K의 나머지를 미리 구해둘 필요가 있었다.
(a⋅b)modc=[(a mod c)⋅(b mod c)] modc

10^0 mod K = 1
10^1 mod K = (1 10) mod K = A
10^2 mod K = (A 10) mod K = B... 이런 식으로

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>


using namespace std;

int N, K;
int mCnt = 0;
 
long long dp[1 << 16][101] = { 0 };

string arr[16];

int rem[16] = { 0 };
int powers_for_rem[51] = { 0 };

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

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

	long long total = 1;

	for (int i = 1; i <= N ; i++)
	{
		total *= i;
	}
	cin >> K;

	for (int i = 0; i < N; i++)
	{
		rem[i] = 0;

		for (char c: arr[i])
		{
			rem[i] = (rem[i] * 10 +( c - '0')) % K; //미리 나머지 구해두기
		}
	}

	powers_for_rem[0] = 1 % K;

	for (int i = 1; i < 51; i++)
	{
		powers_for_rem[i] = (powers_for_rem[i - 1] * 10) % K; //10의 제곱에 대한 나머지를 구해서 나중에 연산할 때 최적화를 위해
	}

	dp[0][0] = 1;

	for (int P = 0; P < (1 << N); P++)
	{
		for (int remain = 0; remain < K; remain++)
		{
			if (dp[P][remain] == 0)
				continue;

			for (int i = 0; i < N; i++)
			{
				if (P & (1 << i)) continue;

				int nextP = P | (1 << i);
				int nextRemain = (remain * powers_for_rem[arr[i].length()] + rem[i]) % K; //미리 계산한 10의 제곱에 대한 나머지를 현재 나머지에 곱한다.

				dp[nextP][nextRemain] += dp[P][remain];
			}
		}
	}
	
	long long r = gcd(dp[(1 << N) - 1][0],total);

	total /= r;
	dp[(1 << N) - 1][0] /= r;


	cout << dp[(1 << N) - 1][0] << "/" << total;


	return 0;
}