BOJ1086 박성원

 

 

 

1086 박성원

 

길이 50 이하의 자연수가 N(≤15)개 주어질 때

주어진 모든 자연수를 한 번씩 사용하여 이어 붙여 만든 자연수가

100이하의 자연수 K로 나누어 떨어질 확률을 구한다.

 

example.

(A) N=3 K=27 { 104, 4, 90 }

104490  104904  410490  490104  901044  904104

여섯 개 중 세 개만 나누어 떨어지므로 1/2 출력

 

(B) N=3 K=13 { 12, 2, 2 } 

1222  1222  2122  2212  2122  2212

여섯 개 중 두 개만 나누어 떨어지므로 1/3 출력

* s[0]="12", s[1]="2", s[2]="2"일 때,

  s[0]+s[1]+s[2]="1222"와 s[0]+s[2]+s[1]="1222"를 모두 세야 한다. (순열 방식이 다름)

 

---

어떤 자연수를 선택했는지를 비트로 표시하고, 해당 자연수를 K로 나눈 나머지가 k인 경우의 수를 센다.

즉 dp[ state ][ mod ]의 값은

state: 지금까지 선택한 수를 이진수로 표시한 값

mod: 이어붙인 수의 나머지

일 때 그런 조합의 개수를 말한다.

 

그리고 다음을 이용해 dp 배열을 구한다.

ABCDE % K

= (AB000 % K + CDE % K) % K

= ((AB % K) * (1000 % K) + CDE % K) % K

 

따라서 자연수 N개를 입력받은 후

각 자연수를 K로 나눈 나머지와

$10^n$ $\left ( 1\leq n\leq 50 \right )$을 K로 나눈 나머지를 미리 구해두고 계산을 하는 것이 편하다.

 

 

---

아래는 문자열로 입력받은 자연수 s를 K로 나눈 나머지를 구하는 함수

int GetMod_s(string s) {
	int res = 0;
	for (int i = 0; i < s.size(); ++i) {
		res = (res * 10 + ((int)(s[i] - '0'))) % K;
	}
	return res;
}

* string을 int로 나누는 연산이라 생각보다 쉽게 구현할 수 있다.

 

 

dp배열은 아래와 같이 구한다.

	for (int cur = 1; cur < FIN; ++cur) {
		for (int mod = 0; mod < K; ++mod) {
			if (!dp[cur][mod]) continue;

			for (int idx = 0; idx < N; ++idx) {
				if (cur & (1 << idx)) continue;

				int nxt = cur | (1 << idx);
				int newmod = (mod * ten[s[idx].size()] + num[idx]) % K;
				dp[nxt][newmod] += dp[cur][mod];
			}
		}
	}

* 이때 비트연산은 for문으로 돌리면 된다.

이전에 큐를 사용했는데 그럴 필요가 없음을 깨달았다,,, 큐를 사용했던 이유는

1이 1개인 수(1, 2, 4, 8, 9, ...), 2개인 수(3, 5, 6, 9, 10, ...)를 확인하고

3개인 수(7, 11, 14, ...)를 확인하는 순서 때문이었는데

어차피 7(0111)을 필요로 하는 값은 1111, 10111, ... 등으로 7보다 크고

9(1001)처럼 7보다 커도 7의 영향을 받지 않는 수가 있기 때문에 굳이 그럴 필요가 없다.

 

** ten 배열을 사용하지 않으면 매 연산마다 10을 계속 곱해주다가 시간초과가 나버렸다.

 

***

 

 

이렇게 구한 dp[$2^N-1$][0]와 전체 경우의 수($N!$)의 GCD를 이용해 확률을 출력하면 된다.

 

 

전체 코드

 

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

int N, K, FIN;
string s[15];
long long dp[32768][100];

long long GCD(long long A, long long B) {
	long long R = A % B;
	return (R == 0) ? B : GCD(B, R);
}
int GetMod_s(string s) {
	int res = 0;
	for (int i = 0; i < s.size(); ++i) {
		res = (res * 10 + ((int)(s[i] - '0'))) % K;
	}
	return res;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int num[15], ten[51];
	
	cin >> N; FIN = (1 << N) - 1;
	for (int i = 0; i < N; ++i) cin >> s[i];
	cin >> K;
    
	// Get num & ten
	for (int i = 0; i < N; ++i) {
		num[i] = GetMod_s(s[i]);
		dp[1 << i][num[i]]++;
	}
	ten[0] = 1;
	for (int i = 1; i < 51; ++i) ten[i] = (ten[i - 1] * 10) % K;

	// Get dp
	for (int cur = 1; cur < FIN; ++cur) {
		for (int mod = 0; mod < K; ++mod) {
			if (!dp[cur][mod]) continue;

			for (int idx = 0; idx < N; ++idx) {
				if (cur & (1 << idx)) continue;

				int nxt = cur | (1 << idx);
				int newmod = (mod * ten[s[idx].size()] + num[idx]) % K;

				dp[nxt][newmod] += dp[cur][mod];
			}
		}
	}

	// Get ANS
	long long Total = 1;
	for (long long n = 2; n <= N; ++n) Total *= n;

	if (!dp[FIN][0]) cout << "0/1";
	else if (dp[FIN][0] == Total) cout << "1/1";
	else {
		long long gcd = GCD(Total, dp[FIN][0]);
		cout << (dp[FIN][0] / gcd) << "/" << (Total / gcd);
	}
	return 0;
}

 

와 주절주절

 

1. 처음엔 이렇게 생각했다. 이렇게 해결할 수 없다는 걸 깨달았지만

 

 

2. 큐 사용 + ten없이 10을 계속 곱해줌으로 시간초과였다.

와중에 나는 괄호 잘못쓰고 친구는 인덱스 잘못쓰고 난리났었다. 역시 스터디는 남이랑 해야지,, 내 코드 나만봐선 오류 찾기 쉽지 않다.