[ 백준 3671 ] 산업 스파이의 편지 (C++)

백준의 산업 스파이의 편지(3671) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 주어진 수를 조합해서 소수인지 아닌지 판단 후, 소수의 갯수를 출력하는 문제이다.

   이 문제에서는 순열을 구현할 줄 알아야 한다. 순열인 이유는, 순서에 따라 결과가 달라지기 때문이다.

   예제입력1 을 한번 봐보자. 17 이라는 숫자가 주어졌다. 이 때 우리가 만들 수 있는 순열로는 { 1 } , { 7 } , { 17 } , { 71 }

   총 4개를 만들 수 있다. 즉, 17과 71, 같은 조합이지만 순서에 따라서 결과가 달라질 수 있기 때문에 순열을 구현할 줄 알아야 한

   다. 아직 순열을 구현할 줄 잘 모른다면 아래 링크를 타고 참고하도록 하자 !

   [ 순열 구현하기 알아보기(Click) ]

  

2) 우리는 1)에서 이 문제는 순열을 구현할 줄 알면, 쉽게 해결할 수 있다는 것을 알았다. 지금부터는 중복을 어떻게 처리해야 되는

   지 또 왜 처리해줘야 하는지 알아보자.

   예를들어서 "11111"이라는 숫자가 주어졌다고 생각해보자. 순열을 구현한다면 아마, { 1 }, { 11 } , { 111 } , { 1111 }, { 11111} 이

   나올 것이다. 하지만, 위의 순열을 구현하는 글을 읽고 구현했다면 이 5개 보다 훨씬 더 많은 결과를 출력해낼 것이다.

   컴퓨터 입장에서는 { 11 } , { 11 } 이라고 해도, 다른 숫자로 알기 때문이다.

   더 쉽게, 위에 "11111" 에서 앞에 1부터 순서대로 1~5번까지 번호를 붙였다고 생각해보자.

   { 11 } 이라는 결과가 나왔다면, 이 { 11 } 은, (1, 2) , (1, 3), (1, 4), (1, 5), (2, 1) .... (5, 4) 까지 엄청나게 많이 나올 것이다.

   하지만, 우리입장에서는 1번 + 2번이 합쳐진 11인지, 3번 + 4번 이 합쳐진 11인지 관심없다. 우리에게는 똑같은 11일뿐.

   11이 소수라면 정답갯수에 ++를 하면되고, 그게 아니라면 안하면 끝이다. 굳이 모든 11에 대해서 이를 판단해줄 필요는 없다.

   따라서 우리는 중복을 처리해줘야 한다.

   본인은 이 중복처리를 위해서 set을 사용해주었다. 배열로 관리하기에는 백만칸이 넘어가기 때문에, 중복체크 하는 과정에서

   제대로 처리를 못하는 경우가 발생했었기 때문이다.

  

   중간중간, 중복처리를 하기 위해서 값을 모두 합하는 부분({ 1, 7 } 인 경우 이를 17 로 만드는 과정) , 소수인지 판단하는 부분

   같은 경우는 어렵지 않으니 소스코드만 참고해도 쉽게 이해할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<cstring>
 
#define endl "\n"
using namespace std;
 
string Inp;
bool Select[7];
int Len, Answer;
 
vector<char> V;
set<int> Visit;
 
void Initialize()
{
    Inp.clear();
    Visit.clear();
    memset(Select, false, sizeof(Select));
    Answer = 0;
    Len = 0;
    V.clear();
}
 
void Input()
{
    cin >> Inp;
    Len = Inp.length();
}
 
bool Calculate(int Data)    // 소수인지 판단하는 함수
{
    if (Data < 2) return false;
    for (int i = 2; i * i <= Data; i++)
    {
        if (Data % i == 0) return false;
    }
    return true;
}
 
int SumOf_Vector()
{
    int Sum = 0;
    for (int i = 0; i < V.size(); i++)
    {
        Sum = Sum + (V[i] - '0');
        if (i != V.size() - 1) Sum = Sum * 10;
    }
    return Sum;
}
 
void DFS(int Cnt)
{
    if (Cnt > Len) return;
 
    if (V.size() != 0)
    {
        int Value = SumOf_Vector();
        if (Visit.find(Value) == Visit.end())
        {
            Visit.insert(Value);
            if (Calculate(Value) == true) Answer++;
        }
    }
 
    for (int i = 0; i < Len; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(Inp[i]);
        DFS(Cnt + 1);
        Select[i] = false;
        V.pop_back();
    }
}
 
void Solution()
{
    DFS(0);
    cout << Answer << endl;
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}