Boj 1086) 박성원

문제

백준 1086

방법 1

설명

100 보다 작은 자연수 K 로 나누어지는 조합을 구해야한다. 쌩으로 구하면 O(\(K!\)) 의 시간복잡도로 제시간에 구할 수 없지만, 모든 수가 K 나머지로 표현될 수 있다는 점을 통해 빠르게 구할 수 있다. 사실 순열을 경로로 생각하면 외판원 문제랑 똑같다.

주어진 수 중에 \(N'\) 개만을 사용한 부분수열의 경우는 \(N'!\) 로 매우 큰 수이다. 하지만 우리가 주목해야할 것은 수열을 합친 정수이지 수열 그 자체가 아니다. 사용한 수의 갯수와 \(K\) 로 나눈 나머지로 바꾼다면 비둘기집의 원리로 최대 \(K\) 개의 서로다른 수열로 압축할 수 있다. 이러한 부분수열의 뒷부분에 새로운 수를 추가할 수 있고, 그렇게 만들어진 수열을 합친 정수는 다음 두가지를 더한 값이다.

1. 이전 부분수열을 합친 정수에 새로운 수의 자릿수만큼 10 이 제곱되고 다시 \(K\) 로 나눈 수.
2. 새로운 수를 \(K\) 로 나눈 수.

사용한 숫자의 조합과 합친 정수를 \(K\) 로 나눈 나머지가 같은 부분수열들은 이후에 수를 추가해서 합친 정수의 값이 항상 같다. 그러므로 두가지 정보(사용한 수의 조합, 합친 정수) 만으로 메모이제이션을 사용할 수 있다.

주의

이때 dp[][] 는 가능한 경우의 수가 크므로 long long 이 필요함에 주의하자. 그리고 k, n 은 long long 으로 굳이 할 필요가 없다. 크게는 100ms 이상 결과가 차이가 나니 주의하자.

시간 복잡도

O(\(2^K K\))

코드

using ll = long long;
int n, k;
string arr[15];
int modK[15], modKTen[51];
ll dp[1 << 15][100];

int MOD(const string& in, int k)
{
	int cur = 0; int mul = 1;
	for (auto iter = in.begin(); iter != in.end(); iter++)
	{
		cur *= 10;
		cur += (*iter - '0');
		cur %= k;
	}
	return cur;
}

ll DFS(int visits, int res)
{
	if (dp[visits][res]) return dp[visits][res] - 1;
	if (visits == (1 << n) - 1) return res == 0;

	for (int i = 0; i < n; i++)
	{
		if (visits & (1 << i)) continue;
		int new_res = (res * modKTen[arr[i].length()] + modK[i]) % k;
		dp[visits][res] += DFS(visits | (1 << i), new_res);
	}
	return dp[visits][res]++;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	cin >> k;

	modKTen[0] = 1;
	for (int i = 1; i < 51; i++) modKTen[i] = modKTen[i - 1] * 10 % k;
	for (int i = 0; i < n; i++) modK[i] = MOD(arr[i], k);

	ll nom = DFS(0, 0);
	ll denom = 1; for (int i = 2; i <= n; i++) denom *= i;
	ll ggcd = gcd(nom, denom);
	nom /= ggcd; denom /= ggcd;
	cout << nom << '/' << denom;
}

방법 2

설명

방법 1을 Bottom-Up 방식으로 고친 것이다. (수의 조합, 합친 정수) 의 모든 경우에 수에 대해서 점화식을 수행한다. 또한 편의상 방법 1에서는 dp[visits][mod] 가 현 생태에서 수를 추가해 나누어 떨어지는 경우의 수라면, 방법 2에서는 현 상태가 가능한 경우의 수를 의미한다.

이때 점화식을 수 1개만을 조합한 경우, 2개만을 조합한 경우 … 이렇게 가야지 섞이면 제대로 된 답을 얻을 수 없다. 하지만 위와 같은 경우는 다르다. 15 == 0b1111 가 완성되기 위해 먼저 계산되어야 할 dp[][]는 visits 가 0b1110, 0b1101, 0b1011, 0b0111 인 경우이다. 그리고 이 경우들은 모두 15보다 작은 숫자이다. 이는 재귀적으로도 성립한다. 그래서 1부터 순서대로 계산해나가도 상관이 없다.

시간 복잡도

O(\(2^K K\))

코드

using ll = long long;
ll dp[1 << 15][100];
int n, k;
string arr[15];
int modK[15], modKTen[51];

int MOD(const string& in, int k)
{
	int cur = 0; int mul = 1;
	for (auto iter = in.begin(); iter != in.end(); iter++)
	{
		cur *= 10;
		cur += (*iter - '0');
		cur %= k;
	}
	return cur;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	cin >> k;

	modKTen[0] = 1;
	for (int i = 1; i < 51; i++) modKTen[i] = modKTen[i - 1] * 10 % k;
	for (int i = 0; i < n; i++) modK[i] = MOD(arr[i], k);

	dp[0][0] = 1;
	for (int mask = 0; mask < (1 << n) - 1; mask++)
		for (int i = 0; i < n; i++)
			if ((mask & (1 << i)) == 0)
				for (int j = 0; j < k; j++)				
					if (dp[mask][j])
					{
						int next_mask = mask | (1 << i);
						int next_mod = (j * modKTen[arr[i].length()] + modK[i]) % k;
						dp[next_mask][next_mod] += dp[mask][j];
					}				
		
	ll nom = dp[(1 << n) - 1][0];
	ll denom = 1; for (int i = 2; i <= n; i++) denom *= i;
	ll ggcd = gcd(nom, denom);
	nom /= ggcd; denom /= ggcd;
	cout << nom << '/' << denom;
}