[BOJ_22493] 수

설명

---

처음에 모듈화를 하지 않고 줄줄 풀었더니 계속 어딘가에서 예외 상황이 발생해서 틀렸습니다를 반복해서 볼 수 있었던 코드다. 사실 세부 내용 자체는 어렵지 않다 에리토스테네스의 체를 활용해서 소수 구하고 그것을 더하고 또는 곱한 것을 이용해서 값을 찾는것을 반복하는 것인데 세부 모듈화를 하지 않으면 에러를 찾기 힘들것 같다.

 

그리고, 해당 100_000 이 부분은 최대 K 값이 될 수 있는 부분을 참고한 것으로 K는 최대 10^5승 까지 가능하다. 그래서, 소수의 곱을 (99991*99991= 9998200081)이런식으로 들어 왔을때, (9998200081  > 2147483647) int 범위를 넘칠 경우를 대비해서 사용했다.

 

코드

---

package Math;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_22493 {
    static int K,cnt = 0;
    static int M = 0;
    static boolean visited[];
    static Set<Integer> set;
    static Set<Integer> set1;

    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        K = Integer.parseInt(tk.nextToken());
        M = Integer.parseInt(tk.nextToken());

        visited = new boolean[10];
        List<Integer> list = new ArrayList<>();

        makePrime(list);

        Set<Integer> multi = new HashSet<>();
        Set<Integer> sum = new HashSet<>();
        makeSumAndMulti(list, multi, sum);
        set = multi;
        set1 = sum;
        make_num(0,"");

        System.out.println(cnt);
    }

    private static void makePrime(List<Integer> list) {
        list.add(2);
        boolean check = false;
        for(int i = 3; i <= 100_000; i++){
            check = false;
            for(int j = 2; j*j <= i; j++){
                if(i % j == 0){
                    check = true;
                    break;
                }
            }
            if(!check){
                list.add(i);
            }
        }
    }

    private static void makeSumAndMulti(List<Integer> list, Set<Integer> multi, Set<Integer> sum) {
        for (int i = 0; i < list.size(); i++){
            for (int j = i; j < list.size(); j++){
                if(i != j){
                    int n = list.get(i) + list.get(j);
                    if(n > 100_000){
                        continue;
                    }else {
                        sum.add(n);
                    }
                    long n1 = 1L * list.get(i) * list.get(j);
                    if(n1 > 100_000){
                        continue;
                    } else {
                        multi.add((int)(n1));
                    }
                }else{
                    long n1 = 1L * list.get(i) * list.get(j);
                    if(n1 > 100_000){
                        continue;
                    } else {
                        multi.add((int)(n1));
                    }
                }
            }
        }
    }

    private static void make_num(int idx, String s){
        if(K == idx){
            if(Integer.parseInt(s) < Math.pow(10,K-1)){
                return;
            }
            int tmp = Integer.parseInt(s);
            if(set1.contains(tmp)){
                while (tmp % M == 0){
                    tmp /= M;
                }
                if(set.contains(tmp)){
                    cnt++;
                }
            }

            return;
        }
        for(int i = 0; i <= 9; i++){
            if(visited[i] == true){
                continue;
            }else {
                visited[i] = true;
                make_num(idx + 1, s + i);
                visited[i] = false;
            }
        }
    }
}

22943번: 수