백준 22943 수 (C++)

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

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> prime;
int ans = 0;
bool visit[10];
int k, m;

void solve(int cnt, int num) {

    if (cnt == k) {
        int s = 0;
        int e = prime.size() - 1;
        bool isSum = false;

//        서로 다른 두 개의 소수의 합으로 나타낼 수 있는 경우
        while (s < e) {
            int sum = prime[s] + prime[e];
            if (sum == num) {
                isSum = true;
                break;
            } else if (sum < num) {
                s++;
            } else {
                e--;
            }
        }

//        M으로 나누어 떨어지지 않을때까지 나눈 수가 두 개의 소수의 곱인 경우, 이 때, 두 개의 소수가 같아도 된다.

        while (num % m == 0) {
            num /= m;
        }

        s = 0;
        e = prime.size() - 1;
        bool isMul = false;

        while (s <= e) {
            long long mul = prime[s] * prime[e];
            if (mul == num) {
                isMul = true;
                break;
            } else if (mul < num) {
                s++;
            } else {
                e--;
            }
        }

        if (isSum && isMul) {
            ans++;
        }

        return;

    }

    for (int i = 0; i < 10; i++) {
        if ((i == 0 && cnt == 0) || visit[i]) {
            continue;
        }

        visit[i] = true;
        solve(cnt + 1, num * 10 + i);
        visit[i] = false;

    }

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> k >> m;



    for (int i = 2; i < pow(10, k); i++) {
        bool isPrime = true;
        for (int j = 2; j*j <= i; j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            prime.push_back(i);
        }
    }

    solve(0, 0);

    cout << ans;

    return 0;
}

1. 문제

k와 m이 주어진다. 서로 다른 숫자로 이루어진 k 자리의 수 중 다음 조건을 만족하는 수의 개수를 구하라

• 서로 다른 두 소수의 합으로 나타낼 수 있다.
• m으로 나누어 떨어지지 않을 때 까지 나눈 수가 두 소수의 곱으로 나타낼 수 있다.

2. 풀이

우선 조건에 부합하는 숫자를 구하기 위해서는 소수가 필요하다. 이는 에라토스테네스의 체로 구할 수 있다.

    for (int i = 2; i < pow(10, k); i++) {
        bool isPrime = true;
        for (int j = 2; j*j <= i; j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            prime.push_back(i);
        }
    }

각 숫자에 대해 제곱근 이하의 수 까지 나누어지는 지 확인하여 소수인지를 판별한다. 그 다음은 숫자를 만들기 위해 재귀를 활용하였다.

    for (int i = 0; i < 10; i++) {
        if ((i == 0 && cnt == 0) || visit[i]) {
            continue;
        }

        visit[i] = true;
        solve(cnt + 1, num * 10 + i);
        visit[i] = false;

    }

k 가지의 숫자는 한 번씩만 사용되어야 하며, 수의 맨 앞에 0이 들어올 수 없다. 이를 걸러주고, 백트래킹으로 숫자를 만들어 준다. 연산이 끝나면 해당 숫자는 다시 사용할 수 있으므로 visit[i]=false로 되돌린다.

        int s = 0;
        int e = prime.size() - 1;
        bool isSum = false;

//        서로 다른 두 개의 소수의 합으로 나타낼 수 있는 경우
        while (s < e) {
            int sum = prime[s] + prime[e];
            if (sum == num) {
                isSum = true;
                break;
            } else if (sum < num) {
                s++;
            } else {
                e--;
            }
        }

k 자리의 숫자를 만들었다면 모든 소수 중 두 개를 뽑아 더한 값으로 해당 숫자를 만들 수 있는 지 확인한다.

//        M으로 나누어 떨어지지 않을때까지 나눈 수가 두 개의 소수의 곱인 경우, 이 때, 두 개의 소수가 같아도 된다.

        while (num % m == 0) {
            num /= m;
        }

        s = 0;
        e = prime.size() - 1;
        bool isMul = false;

        while (s <= e) {
            long long mul = prime[s] * prime[e];
            if (mul == num) {
                isMul = true;
                break;
            } else if (mul < num) {
                s++;
            } else {
                e--;
            }
        }

두 번째 조건을 확인하기 위해 m으로 더 이상 나누어 떨어지지 않을 때 까지 m으로 나누고, 이 역시 모든 소수 중 두 개를 뽑아 곱한 값으로 나타낼 수 있는 지 확인한다.

        if (isSum && isMul) {
            ans++;
        }

두 조건을 모두 만족하였다면 해당 숫자의 개수를 세어준다.

연산이 모두 끝나고 이를 출력하면 정답을 구할 수 있다.