[백준] 22943번 : 수 (C++)

22943번 : 수

---

문제)

0부터 9까지 K가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수들의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다.

1. 서로 다른 두 개의 소수의 합으로 나타낼 수 있는 경우
2.  M으로 나누어 떨어지지 않을때까지 나눈 수가 두 개의 소수의 곱인 경우, 이 때, 두 개의 소수가 같아도 된다.

예를 들어, K$ 1이고 M$ 11인 경우로 생각해보자. 한자리 수 중 1번 조건을 만족하는 수는 5, 7, 8, 9이고 2번 조건을 만족하는 수는 4, 6, 9가 있다. 이 두개의 조건을 둘다 만족하는 수는 9이므로 이 경우에는 1개이다.

 

 

입력 :

첫 번째 줄에 K와 M 주어진다.

 

 

 

출력 :

2가지 조건을 만족하는 수의 개수를 출력한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <math.h>
 
using namespace std;
 
int k, m;
int visited[10];
int cnt;
vector<int> prime_number;
 
void check(int x);
 
void prime()
{    
    // 에라토스테네스의 체를 이용하여 k자리 수까지의 소수를 구한다.
    for (int i = 2; i <= pow(10, k); i++)
    {
        int flag = 0;
 
        for (int j = 2; j * j <= i; j++)
        {
            if (i % j == 0)
            {
                flag = 1;
                break;
            }
        }
 
        if (!flag) prime_number.push_back(i);
    }
}
 
void recur(int cur, int total)
{
    if (cur == k)
    {    // k자리 수를 만들었다면
        // 조건을 만족하는지 확인작업을 한다.
        check(total);
        return;
    }
 
    for (int i = 0; i < 10; i++)
    {    
        // 1번째 자리의 수는 0이 올 수 없음
        if (cur == 0 && i == 0) continue;
        // 사용한 수는 또 다시 사용할 수 없다.
        if (visited[i]) continue;
 
        visited[i] = 1;
        recur(cur + 1, total * 10 + i);
        visited[i] = 0;
    }
}
 
void check(int x)
{    // 투포인터를 사용하여 소수 2개를 골라내었다.
    int s = 0;
    int e = prime_number.size() - 1;
 
    // 서로 다른 두 개의 소수의 합으로 나타낼 수 있는 경우
    bool flag1 = 0;
    while (s < e) // 서로 다른 두 개이므로 s == e는 고려하지 않는다.
    {    
        // 조건을 만족한 경우
        if (prime_number[s] + prime_number[e] == x)
        {
            flag1 = 1;
            break;
        }
        // 오름차순이므로 s++
        else if (prime_number[s] + prime_number[e] < x)
        {
            s++;
        }
        else if (prime_number[s] + prime_number[e] > x)
        {
            e--;
        }
    }
 
    // m으로 나누어 떨어지지 않을때까지 나누어준다.
    while (x % m == 0)
    {
        x /= m;
    }
 
    // 포인터를 초기화한다.
    s = 0;
    e = prime_number.size() - 1;
 
    bool flag2 = 0;
    while (s <= e)    // 두 개의 소수가 같아도 되므로 s == e 포함
    {    // 두 소수의 곱으로 표현이 가능한 경우 
        if (prime_number[s] * prime_number[e] == x)
        {
            flag2 = 1;
            break;
        }
        else if (prime_number[s] * prime_number[e] < x)
        {
            s++;
        }
        else if (prime_number[s] * prime_number[e] > x)
        {
            e--;
        }
    }
 
    // 두 조건을 모두 만족한 경우 cnt를 1개 더해준다.
    if (flag1 && flag2)
    {
        cnt++;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> k >> m;
 
    prime();
 
    recur(0, 0);
 
    cout << cnt;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/22943 

22943번: 수