[22943] 수

✔ 수

[백준 22943]

코드 구현하기

/*
 * 문제 분석하기
 * : 소수들을 찾아, 두 소수가 조건을 만족하는지 확인하도록 함
 */

/* 
 * 손으로 풀어보기
 * 1. K가지의 숫자를 가지고 만들 수 있는 가장 큰 수까지의 소수 찾기
 * 2. 소수 쌍을 가지고 조건 1과 조건 2의 경우의 수 만들기
 * 3. K가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 선택해 조건1, 2 확인하기
 * 4. 조건을 만족하는 수의 개수 출력
 */

/*
 * 22943) 수
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int K, M;
    static int limit; // limit(K개의 서로 다른 숫자로 만들 수 있는 수의 최대값)
    static ArrayList<Integer> primeNumberList; // primeNumberList(소수들 리스트)
    static HashSet<Integer> sumSet; // sumSet(조건 1을 만족하는 수들)
    static HashSet<Integer> multiSet; // multiSet(조건 2를 만족하는 수들)
    static boolean[] visited = new boolean[10]; // visited(수를 만들기 위한 방문 유무 배열)
    static int answer = 0; // answer(조건을 만족하는 수의 개수)

    /*
     * 소수 찾기 준비하기
     */
    static void init(StringTokenizer st) {
        K = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        String s = "";
        for (int i = 9; i >= 0; i--) {
            s += i;
            if (s.length() == K) {
                break;
            }
        }
        limit = Integer.parseInt(s);
    }

    /*
     * K가지의 숫자를 가지고 만들 수 있는 가장 큰 수까지의 소수 찾기
     */
    static void findPrimeNumber() {
        boolean[] arr = new boolean[limit + 1];
        for (int i = 2; i <= (int) Math.sqrt(limit); i++) { // 에라토스테네스 방법으로 소수 구하기
            if (arr[i]) {
                continue;
            }
            for (int j = i + i; j <= limit; j = j + i) {
                arr[j] = true;
            }
        }

        primeNumberList = new ArrayList<Integer>();
        for (int i = 2; i <= limit; i++) {
            if (!arr[i]) {
                primeNumberList.add(i);
            }
        }
    }

    /*
     * 소수 쌍을 가지고 조건 1과 조건 2의 경우의 수 만들기
     */
    static void findSumAndMulti() {
        sumSet = new HashSet<Integer>();
        multiSet = new HashSet<Integer>();

        for (int i = 0; i < primeNumberList.size(); i++) {
            for (int j = i; j < primeNumberList.size(); j++) {
                int pn1 = primeNumberList.get(i);
                int pn2 = primeNumberList.get(j);

                int sum = pn1 + pn2;
                if (pn1 != pn2) {
                    if (sum <= limit) {
                        sumSet.add(sum); // 조건 1을 만족하는 수들
                    }
                }

                long multi = 1L * pn1 * pn2;
                if (multi <= limit) {
                    multiSet.add((int) multi); // 조건 2를 만족하는 수들
                }
            }
        }
    }

    /*
     * K가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 선택하기
     */
    static void selectNumber(int depth, int number) {
        if (depth == K) {
            if (isValid(number)) {
                answer++;
            }
            return;
        }
        for (int i = 0; i <= 9; i++) {
            if (i == 0 && depth == 0 || visited[i]) {
                continue; // 수의 맨 앞이 0이거나, 이미 사용한 수라면 넘어감
            }
            visited[i] = true;
            selectNumber(depth + 1, number * 10 + i);
            visited[i] = false;
        }
    }

    /*
     * 조건1, 2 확인하기
     */
    static boolean isValid(int number) {
        if (!sumSet.contains(number)) {
            return false; // 조건 1을 만족하지 않는다면
        }
        while (number % M == 0) {
            number /= M;
        }
        if (!multiSet.contains(number)) {
            return false; // 조건 2를 만족하지 않는다면
        }
        return true; // 조건 1, 2를 모두 만족한다면
    }

    /*
     * 조건을 만족하는 수의 개수 출력
     */
    static void print() {
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        init(st);
        findPrimeNumber();
        findSumAndMulti();
        selectNumber(0, 0);
        print();
    }
}