boj, 백준) 1086. 박성원 ( C / C++)

1. 문제 링크

www.acmicpc.net/problem/1086

1086번: 박성원

 

2. 문제 개요

서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 합친 수가 정수 K로 나누어 떨어지는 순열을 구하는 프로그램을 작성하시오.

박성원이 우연히 정답을 맞출 확률을 분수로 출력하는 프로그램을 작성하시오.

 

3. 문제 힌트

 

(1) 숫자의 길이가 최대 50

 - 입력을 string으로 받아서 나머지를 계산해야 함. 손으로 직접 나머지를 구하는 방법 그대로 적용하자. -> O(L), L은 숫자의 길이.

 

(2) 기약 분수로 나타내기

 - 기약분수는 서로 더 이상 약분할 수 없는 것. 최대공약수를 구해서 1번만 나누어주자.

 

(3) 새로운 숫자의 나머지 구하기

 - 123이라는 숫자에 456이라는 숫자가 붙었다. 그러면, 123*100 + 456으로 표현할 수 있다.

123456 % k = (123*100)%k + 456%k 로 나타낼 수 있고, (123%k)*(100%k) +456%k 로 나타낼 수 있다.

 

이전 숫자들의 나머지를 미리 알고 있으면 새로 만든 숫자의 나머지도 바로 알 수 있다.

 

(4) 어떤 숫자를 썼는지 비트로 표현하자.

 

4. 문제 풀이

우선, dp를 사용하지 않는다면 시간복잡도는 적어도 N!이 된다.

 

큰 문제를 작은 문제로 쪼갤 수 있고.. 이전의 값만 알고 있다면 빠르게 만들어 나갈 수 있다. (이전의 값이 최적의 값이어야 함.)

 

dp를 다음과 같이 정의한다.

dp[i][k], i는 bit로 생각하고,

만약 n이 4일 때, i = 6 -> 0110 , 2번째 3번째 값을 뽑아 만든 순열로 정의.

k는 i와 같은 상황일 때, 나머지가 k인 순열의 개수이다.

즉, n이 4일 때 dp[6][2]는 2번째, 3번째 값을 뽑아 만든 순열 중 나머지가 2인 순열의 개수라고 정의한다.

 

상태 전이라고 해야 할까.. 숫자가 전이하는 것을 그림으로 보면.. 다음과 같다. 여기서 n=4.

 

위의 그림처럼 값이 전달된다. 

원 안의 값은 dp[i][k], 상태를 의미한다.

 

0000, 아무것도 안 뽑은 상태에서 1개를 뽑은 상태로 넘어간다.

이때 초기값 dp[0][0] = 1로 둔다.

 

처음 상태 0에서  0번째 bit에서 n번째 비트까지 체크해본다.

bit가 0이면 그 자리에 1을 넣고 값을 누적시켜줘야 하는데, dp[다음 상태][새로운 나머지] += dp[현재 상태][현재 나머지]가 된다.

 

나머지는 3.(3)에 적은 대로 적용하면 된다.

새로운 나머지 = (현재 나머지 * 10^새로운 숫자의 자릿수%k + 새로 추가되는 수 % k) % k

 

 

그런데 여기서 상태를 넘어갈 때,

예를들어 상태 13은 상태 9, 상태 12에서 온다. 13에 도달해서 상태 15의 값에 값을 누적시켜줄 때, 만약 상태 9, 12가 완벽하게 누적되지 않았다면 최적해가 보장되지 않는다.

 

반복순서 - BFS

그래서 다음과 같이 반복순서를 BFS로 억지로 만들어 줬다.

물론 답은 정답이었지만 시간이 4배가 더 나와(약 450ms) BFS를 쓰지 않고도 최적해가 보장되면서 값을 쌓아나갈 수는 없을까..라고 생각해봤는데...

 

그냥 반복을 0, 1, 2, ... , 2^n-1로 해도 문제가 되지 않는 것을 알 수 있었다.

 

애초에 or 연산을 통해 0이었던 bit을 1로 증가시켜주면서 상태를 누적시켰기 때문에,

자신을 가리키고 있는 상태들은 모두 자신보다 값이 작다. 따라서 그냥 0부터 반복해도 전혀 문제가 되지 않았다.

 

그래서, 모든 상태들을 한번 순회하면서, O(2^N)

n자리의 bit가 0인지 체크하고 O(N)

모든 가능한 나머지에 대해 값을 누적시켜주기 때문에 O(K)

 

시간복잡도는 O(2^N * N * K)라고 할 수 있다.

 

 

5. 코드

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

int n, k;
string s[16];
long long int dp[32768][100]; //[2^15][k]
int cache[51];
int cachestr[15];

//O(L) L is length of string s
int get_mod(const string &s, const int divisor)
{
	int ret = 0;
	for (int i = 0; i < s.length(); ++i) {
		ret *= 10;
		ret += s[i] - '0';
		ret %= divisor;
	}
	return ret;
}

long long GCD(long long lhs, long long rhs)
{
	long long big, small;

	big = max(lhs, rhs);
	small = min(lhs, rhs);

	while (small != 0) {
		long long int remainder = big % small;
		big = small;
		small = remainder;
	}
	return big;
}

void solution()
{
	for(int cur = 0; cur < (1 << n); ++cur){
		for (int i = 0; i < n; ++i) {

			if ((cur & (1 << i)) == 0) {
			
				int nextState = cur | (1 << i);

				for (int j = 0; j < k; ++j) {

					int nextK = ((j * cache[s[i].length()]) % k + cachestr[i]) % k;

					dp[nextState][nextK] += dp[cur][j];
				}
			}
		}
	}

	return;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; ++i)
		cin >> s[i];

	cin >> k;
	
	dp[0][0] = 1;

	cache[0] = 1 % k;
	for (int i = 1; i < 51; ++i) 
		cache[i] = (cache[i - 1] * 10) % k;
	
	for (int i = 0; i < n; ++i) 
		cachestr[i] = get_mod(s[i], k);
	

	solution();

	long long denominator = 1, numerator;

	for (int i = 1; i <= n; ++i)
		denominator *= i;

	numerator = dp[(1 << n) - 1][0];
	long long gcd = GCD(numerator, denominator);

	cout << numerator / gcd << "/" << denominator / gcd;

	return 0;
}

 

 

6. 결과