[백준 22943] 수 [Java]

문제

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

 

---

풀이

0 ~ 9 중에서 서로 다른 K개를 골라 만들 수 있는 수 중 다음을 만족하는 수를 구해야 한다.

• 서로 다른 두 개의 소수의 합으로 나타낼 수 있어야 하고,
• M으로 나누어 떨어지지 않을 때 까지 나눈 수가 두 개의 소수의 곱인 경우이어야 한다.

구현할 부분이 많지만, 하나씩 해결해보자.

0 ~ 9로 K자리 수 만들기

우선 0 ~ 9 중 K개를 골라 수를 만들어야 한다.

숫자를 한 번씩 만 사용해야 하고, 첫 번째는 0이 올 수 없다.

    private static void solve(int digit, int num) {
        if (digit == 0) {
	          // base case
        }
        for (int i = 0; i <= 9; ++i) {
            if ((i == 0 && digit == K) || visited[i]) continue;
            visited[i] = true;
            solve(digit - 1, num * 10 + i);
            visited[i] = false;
        }
    }

digit 가 0이 되면 K가지의 숫자를 모두 사용해 숫자를 다 만들었다. 주어진 조건을 확인 후 만족하는 수를 세면 된다.

문제에서 주어진 조건을 검사하기 위해 우선 소수부터 구하자.

일단 가장 큰 수는 K가 5일 때 만들 수 있는 수 98,765이다.

final static int MAX = 98_765;

에라소트테네스의 채를 사용해 MAX이하의 소수를 모두 구하자.

    private static void initPrimeList() {
        boolean[] isPrime = new boolean[MAX + 1];
        Arrays.fill(isPrime, true);

        isPrime[1] = false;
        final int sqrtN = (int)Math.sqrt(MAX);
        for (int i = 2; i <= sqrtN; ++i) {
            if (isPrime[i]) {
                for (int j = i * i; j <= MAX; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        primeList = new ArrayList<>();
        for (int i = 2; i <= MAX; ++i) {
            if (isPrime[i]) {
                primeList.add(i);
            }
        }
    }

또한 두 소수의 합과, 곱에 대한 리스트를 미리 구하자.

    private static void initCheckList() {
        primeMulList = new HashSet<>();
        primeSumList = new HashSet<>();
        for (int p1 = 0; p1 < primeList.size() - 1; ++p1) {
            for (int p2 = p1; p2 < primeList.size(); ++p2) {
                if (p1 != p2) {
                    final int sumTwoPrime = primeList.get(p1) + primeList.get(p2);
                    if (sumTwoPrime <= MAX) {
                        primeSumList.add(sumTwoPrime);
                    }
                }
                final long mulTwoPrime = (long) primeList.get(p1) * primeList.get(p2);
                if (mulTwoPrime <= MAX) {
                    primeMulList.add((int) mulTwoPrime);
                }
            }
        }
    }

이제 주어진 조건을 검사할 준비가 끝났다. 다시 기저사례를 완성시키자.

        if (digit == 0) {
            if (primeSumList.contains(num)) {
                while (num % M == 0) {
                    num /= M;
                }
                if (primeMulList.contains(num)) {
                    ++res;
                }
            }
            return;
        }

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/22943.java