BOJ 1555 소수 만들기

BOJ 1555 소수 만들기

[분류 : 다이나믹 프로그래밍, 수학]

 

[풀이]

  [순열] N개의 수에 대해서 각 자리수에 어떤 수를 둬도 상관없으므로 최대 N!은 먹고 들어간다. (C++에서 next_permutation 사용)

  [연산 규칙] +,-,*,/ 모두 사칙연산에도 쓸 수 있지만 특히 -는 사칙연산뿐만 아니라 단항 연산에 사용될 수 있다. 즉, 값을 음수면 양수로, 양수면 음수로 바꿀 수 있다.
   단순히 두 피연산자 e1과 e2(e1가 왼쪽에 있을 때)가 있을 때 나올 수 잇는 방법은 아래가 있다

1. e1 + e2
2. e1 - e2
3. e1 * e2
4. e1 / e2

  하지만 음수를 붙여주면 경우의 수는 배로 늘어난다.

5. -e1 - e2
6. -e1 + e2
7. -e1 * e2
8. -e1 / e2

  보면 1.~4.에 음수를 붙힌 것이 나머지 5.~8.이 된다.

  [경우의 수] 하지만 순열 순서에 의해 5.~8.경우가 모두 고려된다. 다만 음수를 양수로 봐꾸는 경우도 고려해야하고 그 반대도 마찬가지다. 즉 -1-2 연산(5.)은 1+2(1.)에 -를 붙여서 표현할 수 있다. 결국 마지막으로 나올 수 있는 모든 수에 대해 절대값을 씌우면 만들 수 있는 소수의 후보군이 된다. 참고로 소수는 1보다 크고 약수가 1과 자기 자신밖에 없는 수이므로 항상 양의 정수를 갖는 걸로 정의가 되어 있다.

  [나올 수 있는 모든 수]
    단순 2차 dp로 해결하자. 마치 행렬 곱셈처럼 구간을 정하고 그 구간 내에서 쪼갤 수 있는 구간이 있으면 쪼개서 1.~4. 연산 규칙으로 두 표현식에 대해 나올 수 있는 모든 수를 고려한다.

dp(i, j).add(dp(i, k) operation dp(k+1, j))

 

  (참고) 에라스토테네스의 체로 소수부를 미리 구해놓고 확인하면 더 빠르게 구할 수 있다

  (참고) 비트마스킹으로도 풀림

 

#include<cstdio>
#include<unordered_set>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX_N = 6, LIMIT = 500001;
int main() {
	int N, k, l, A[MAX_N], mini = 1e9, maxi = -1e9, isPrime, d, sqrtn;
	long long i, j;
	bool chk[LIMIT] = {};
	vector<int> p;
	unordered_set<int> dp[MAX_N][MAX_N];

	for (i = 2; i < LIMIT; i++) if (!chk[i]) {
		p.push_back(i);
		for (j = i * i; j < LIMIT; j += i) chk[j] = 1;
	}

	scanf("%d", &N);
	for (i = 0; i < N; i++) scanf("%d", &A[i]);
	sort(A, A + N);
	do {
		for (i = 0; i < N; i++) for (j = 0; j < N; j++)
			dp[i][j].clear();
		for (i = 0; i < N; i++) dp[i][i].insert(A[i]);
		for (l = 2; l <= N; l++) {
			for (i = 0; i + l - 1 < N; i++) {
				j = i + l - 1;
				for (k = i; k < j; k++) {
					for (auto lt = dp[i][k].begin(); lt != dp[i][k].end(); lt++)
						for (auto rt = dp[k + 1][j].begin(); rt != dp[k + 1][j].end(); rt++) {
							dp[i][j].insert(*lt + *rt);
							dp[i][j].insert(*lt - *rt);
							dp[i][j].insert(*lt * *rt);
							if (*rt > 0 && *lt > 0)
								dp[i][j].insert(*lt / *rt);
						}
				}
			}
		}
		for (auto at = dp[0][N - 1].begin(); at != dp[0][N - 1].end(); at++) {
			d = abs(*at);
			if (d < 2) continue;
			if (d < LIMIT) isPrime = !chk[d];
			else {
				sqrtn = sqrt(d);
				isPrime = 1;
				for (int& pr : p) {
					if (d % pr == 0) {
						isPrime = pr == d;
						break;
					}
					if(pr > sqrtn) break;
				}
			}

			if (isPrime) {
				mini = min(mini, d);
				maxi = max(maxi, d);
			}
		}
	} while (next_permutation(A, A + N));

	if (mini == 1e9) puts("-1");
	else printf("%d\n%d", mini, maxi);
	return 0;
}