[백준/BOJ] 3671번 산업 스파이의 편지

https://www.acmicpc.net/problem/3671

3671번: 산업 스파이의 편지

간단히 생각하면 만들 수 있는 모든 수를 찾아서 그 수가 소수인지 확인하면 되는문제이지만

테스트 케이스가 200개이고 종이의 수가 최대 7개로 1개부터 최대 조각수까지 만들 수 있는 모든 수를 구해야 하기

때문에 시간초과가 된다.

 

따라서 나는 에라토스테네채를 이용하여 7자리 수까지 나올수있는 모든 소수를 구해놓고

테케를 받아 만든 수가 소수인지 아닌지만 체크해 개수를 구했다. 

이문제를 풀때 새롭게 알게된 방법은 두가지로,

1. 순열을 구하는 STL인 next_permutation 

2. 순열을 구하는 생각

이다.

 

처음에는 7개의 숫자가 있다면 1자리인 수부터 7자리인 수까지 만들수있는 모든 수를 구해야한다고생각해서,

3자리 수를 구한다면 7가지의 수 중 3개를 고르고 이 3개를 next_permutation을 사용하려고 했다.  

하지만 이럴 경우 메모리 초과가 나서 틀렸다.

아마 조합을 사용해 숫자배열을 구하고 배열을 인수로받아 순열을 구하는 과정에서 메모리가 초과가 된 것 같다.

이러한 실패를 발판으로 배운 방법은 조합을 사용해 각 자리 수 만큼 숫자를 고른다음 순열을 구하는 것이 아니라

전체 입력받은 숫자배열을 그냥 next_permutaion을 돌려서 1자리일때 돌려서 앞에 한자리만 보고,

또다시 전체 next_permutaion을 돌려가면서 앞의 2자리를 본다. 이런식으로 봐야하는 인덱스만 늘려가면서 

돌리면 굳이 조합으로 특정 개수의 숫자를 고르지 않아도 모든 경우를 볼수 있는 방법이다.

(이미 한번 본 숫자는 map을 이용해 체크해줬다.)

 

2단계로 나눠서 복잡하게 생각했던 방식을 한단계로 줄여서 보는 걸 배운 것이라 상당히 신선하게 충격이면서 

이제라도 알게되어 다행이다라고 생각했다. 

 

 

 

 

 

 

 

< 정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<map>
using namespace std;
bool m[10000000] = { false };
int cnt = 0;
vector<int>nu;
map<int, bool>ck;
void func(void) {
	m[1] = true;
	m[0] = true;
	for (int i = 2; i*i < 10000000; i++) {
		if (!m[i]) {
			for (int j = i*i; j < 10000000; j += i)
			{
				if (!m[j])m[j] = true;
			}
		}
	}
}

void func3(int limit) {
	sort(nu.begin(), nu.end());
	
		do {
			int n = 0;
			for (int i = 0; i <limit; i++) {
				n += pow(10, i)*nu[i];
			}
			if (!m[n]&&ck[n]==NULL) {
				ck[n] = true;
				cnt++;
			}
		} while (next_permutation(nu.begin(),nu.end()));
	return;
}
int main(void) {
	int N;
	scanf("%d", &N);
	func();
	string s;

	for (int t = 0; t < N; t++) {
		cnt = 0;
		nu.clear();
		cin >> s;
		ck.clear();
		for (int i = 0; i < s.length(); i++)nu.push_back(s[i] - '0');
		
		for (int i = 1; i<=nu.size(); i++) {
			func3(i);
		}
		printf("%d\n", cnt);
	}

	return 0;
}