[BOJ] 1086 : 박성원

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

---

DP Bitmasking 비트마스킹

● 최대 길이가 50인 N개의 정수들을 뽑는 경우는 N! 개가 존재한다. N이 최대 15이므로, N! 개를 모두 구하면 시간초과 발생 --> DP 로 문제를 접근

● DP[state][r] := 현재 어떤 정수들을 뽑았는지 state에 비트마스킹을 이용해 표시하고, r 은 K로 나눴을 때 나머지를 의미한다.

 즉, DP[state][r] := state 상태에서 K로 나눴을 때 나머지가 r인 경우의 수

 

DP 배열을 채우기 위해 다음과 같은 정의가 미리 필요하다.

● mul[i] := pow(10, i) % K 를 미리 다 저장해둔다. mod 연산이므로 쉽게 계산 가능

● integer[i] := ( N개의 정수 중 i번 째 정수 ) % K 를 mul[] 을 이용해 미리 계산해놓는다.

 

그럼 DP[ i ] [ j ] 는 다음과 같이 채울 수 있다.

 현재 상태 ( i ) 와 나머지 j 에 대해서 N개의 정수를 다 뒤에 붙여본다. 이때, 이미 현재 상태에서 뽑아서 사용한 정수는 붙여주지 않는다.

 따라서, N개의 정수 중 k 번 째 정수를 뽑았다고 가정하면, i & ( 1 << k ) == 0 이 성립하면 그 정수를 붙여주고, 아니면 이미 사용한 정수이므로 넘어간다.

 이때, 정수를 붙여준다는 것은 현재 상태에서의 나머지 j 를 k번 째 정수의 길이만큼 옆으로 밀어주고, k번 째 정수를 붙여주는 것이므로 j * 10^(k번 째 정수의 길이)를 해주면 되는데, 미리 계산해놓은 mul 배열을 이용해 연산해주고, 뒤에 k번 째 정수를 붙여주는 연산은 integer 배열을 이용하면 된다.

 예시를 통해 익혀보면 현재 "12345" 를 만들었고, "678" 을 붙여주는 연산을 생각해보면 "12345" * 1000 + "678" 을 생각하면 된다.

 이때, 정수론에 의해 ("12345" * 1000 + "678") mod K == ("12345" * 1000) mod K + "678" mod K 와 동일하고, 더 쪼개면 == ("12345" mod K) * (1000 mod K) + ("678" mod K) 로 분해할 수 있다. "12345" mod K 는 우리가 DP[i][j] 에서 j에 해당되는 값이고, (1000 mod K) 는 mul 배열에서 다 계산했고, ("678" mod K) 도 integer 배열에 미리 다 연산해놓았으므로 쉽게 계산할 수 있다.

피드백

 처음에 DP 배열 정의까지는 떠올렸으나, DP 배열 초기화 및 채우는 방법에서 굉장히 오래 헤맸다.

 DP[i][j] 에 그냥 1 ~ N 번 째 정수를 다 붙여본다고 생각하면 간단한데 너무 꼬아서 생각한 것 같다.

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int N, K;
long long dp[1 << 15][100];
long long factorial[16];
int integer[15];
int mul[51];
string list[15];

long long gcd(long long a, long long b) {
	while (b) {
		long long r = a % b;
		a = b;
		b = r;
	}
	return a;
}

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

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> list[i];
	cin >> K;

	for (int i = 0; i < N; i++)
		reverse(list[i].begin(), list[i].end());

	factorial[1] = 1;
	for (int i = 2; i <= 15; i++)
		factorial[i] = factorial[i - 1] * i;

	mul[0] = 1;
	for (int i = 1; i < 51; i++)
		mul[i] = (mul[i - 1] * 10) % K;

	for (int i = 0; i < N; i++) {
		int temp = 0;
		for (int j = 0; j < list[i].length(); j++) {
			temp += ((list[i][j] - '0') * mul[j]) % K;
			temp %= K;
		}
		integer[i] = temp;
	}

	// dp 배열을 채워보자.
	dp[0][0] = 1;
	for (int i = 0; i < (1 << N); i++) {
		for (int j = 0; j < K; j++) {
			for (int k = 0; k < N; k++) { // k번 째 친구를 안쓴애들만 쓰자.
				if ((i & (1 << k)) == 0) { // 현재 상태랑 k 사용이랑 겹치는게 없음.
					// 현재 나머지가 j --> k번 째 수를 사용하면 나머지가 바뀜
					int next = j * mul[list[k].length()];
					next %= K;
					next += integer[k];
					next %= K;
					dp[i | (1 << k)][next] += dp[i][j];
				}
			}
		}
	}

	long long g = gcd(dp[(1 << N) - 1][0], factorial[N]);
	cout << (dp[(1 << N) - 1][0] / g) << '/' << (factorial[N] / g) << '\n';

	return 0;
}

---