[수학] 백준 22943 수

22943번: 수

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

 

# 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    public static final int LIMIT = 98765;
    public static ArrayList<Integer> pn = new ArrayList<>();
    public static HashSet<Integer> pnSum = new HashSet<>();
    public static HashSet<Integer> pnMult = new HashSet<>();
    public static boolean[] v = new boolean[10];
    public static int k, m, answer = 0;

    public static void main(String[] args) throws Exception {
        initPn();
        initPnSumAndMult();
        pn = null;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        bf(0, 0);
        System.out.println(answer);
    }

    public static void initPn() {
        boolean[] isPn = new boolean[LIMIT+1];
        int sqrtN = (int)Math.sqrt(LIMIT);
        for (int i = 3; i <= sqrtN; i+=2) {
            if (isPn[i]) continue;
            int base = i+i;
            while (base <= LIMIT) {
                isPn[base] = true;
                base+=i;
            }
        }
        pn.add(2);
        for (int i = 3; i <= LIMIT; i+=2) {
            if (!isPn[i]) pn.add(i);
        }
    }

    public static void initPnSumAndMult() {
        for (int i = 0; i < pn.size(); i++) {
            for (int j = i; j < pn.size(); j++) {
                int pn1 = pn.get(i);
                int pn2 = pn.get(j);
                long mult = 1l*pn1*pn2;
                if (mult <= LIMIT)
                    pnMult.add((int)mult);
                if (pn1!=pn2) {
                    int sum = pn1+pn2;
                    if (sum <= LIMIT)
                        pnSum.add(sum);
                }
            }
        }
    }

    public static boolean isValid(int cur) {
        if (!pnSum.contains(cur)) return false;
        while (cur%m==0)
            cur/=m;
        if (!pnMult.contains(cur)) return false;
        return true;
    }

    public static void bf(int idx, int cur) {
        if (idx == k) {
            if (isValid(cur))
                answer++;
            return;
        }
        for (int i = 0; i <= 9; i++) {
            if (i==0 && idx==0 || v[i]) continue;
            v[i] = true;
            bf(idx+1, cur*10+i);
            v[i] = false;
        }
    }
}

• K는 최대 5 이므로 최대로 만들 수 있는 값은 '98765'이다. 따라서 98765 이하의 모든 소수의 합 중 98765이하의 합들을 알 수 있어야 한다.
• 마찬가지로 98765 이하의 모든 소수의 곱 중 98765 이하의 곱들을 알 수 있어야 한다. 합과 달리 서로 같아도 된다.
• 따라서 98765 이하의 모든 소수를 에라토스테네스의 체 알고리즘을 통해 구하고, ArrayList 등의 자료구조에 담아둔다. ==  initPn()
• 소수의 합과 곱들을 미리 계산해두자. ==  initPnSumAndMult()
• 0부터 9까지 K가지의 숫자를 한 번씩 사용해 만들 수 있는 모든 수를 탐색해보자. == bf()

 

아래 블로그를 참고했다.

[자바] 백준 22943 - 수 (java)