[백준/실버1] 22943. 수

문제

---

문제

0부터 9까지 K가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수들의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다.

1. 서로 다른 두 개의 소수의 합으로 나타낼 수 있는 경우
2. M으로 나누어 떨어지지 않을때까지 나눈 수가 두 개의 소수의 곱인 경우, 이 때, 두 개의 소수가 같아도 된다.

예를 들어, K가 1이고 M이 11인 경우로 생각해보자. 한자리 수 중 1번 조건을 만족하는 수는 5, 7, 8, 9이고 2번 조건을 만족하는 수는 4, 6, 9가 있다. 이 두개의 조건을 둘다 만족하는 수는 9이므로 이 경우에는 1개이다.

입력

첫 번째 줄에 K와 M주어진다.

출력

2가지 조건을 만족하는 수의 개수를 출력한다.

제한

• 1 ≤ K ≤ 5
• 2 ≤ M ≤ 10^9
• K, M은 정수

풀이

---

접근 방법

• 소수 판별하기

✔️ 에라토스테네스의 체
1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우,11^{2}>120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

 

// 에라토스테네스의 체 구현
    private static void eratos() {
        notSosu[0] = true;
        notSosu[1] = true;
        for (int i = 2; i < Max; i++) {
            if (notSosu[i]) {
                continue;
            } else {
                for (int j = i + i; j < Max; j += i) {
                    notSosu[j] = true;
                }
            }
        }
    }

• 최대 5자리 숫자. 99876 = 27216 가지 경우는 순열로 만든다.
• K자리 숫자를 만들 때마다, 두개의 숫자로 나눠 조건 1을 만족하는지 확인하고(소수인지 확인하고..), 조건 2를 만족하는 지 확인하고...⇒ 너무 계산량이 많고 복잡하다.
• 해결 방법

1. 에라토스테네스의 체 방법을 이용해 모든 소수를 저장한다.
2. 이 소수들의 합을 저장해 놓는다.
3. 이 소수들의 곱을 저장해 놓는다.
4. 2, 3번을 만족하는 지 확인한다.

• 일종의 DP라고 생각한다.
• 이외에도 계산량을 줄이기 위해 K자리 숫자를 만들 때 (재귀 함수) 만들고 있는 숫자를 매개변수로 준다. 기저조건에서 한번에 계산하지 x . 코드로 보는 게 이해가 빠르다.

주의할 점

• int 타입형 long 타입 형. 이 부분 때문의 오류를 잡는 데 시간을 많이 썼다ㅠ
• ArrayOutOfBoundException

    // 두 소수 곱
    private static void makeMult() {
        outer:
        for (int i = 2; i < Max; i++) {
            if (notSosu[i]) continue;

            for (int j = i; j < Max; j++) {
                if (notSosu[j]) continue;

                // 이부분 조심 .. long 타입으로 해야한다.
                // 예를 들어 K = 5 일 때 46349*46349=2148229801 => int이면 음수

                long num = (long) i * (long)j;
                if (num >= Max) continue outer;

                sosuMult[i * j] = true;
            }
        }
    }

코드

---

 

package practice;

//[실버1] 수

import java.util.Scanner;

// 1. 가능한 숫자 만들기 => 최대 5자리 숫자. 9*9*8*7*6 = 27216 가지 경우
// 2. 에라토스테네스의 채로 소수 저장
// 3. 조건 1 만족하는 것들 저장
// 4. 조건 2 만족하는 것들 저장
public class baekjoon_22943 {
    static int K, M;
    static int[] nums;
    static boolean[] visited, notSosu, sosuSum, sosuMult;
    static int answer;
    static int Max;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        K = sc.nextInt();
        M = sc.nextInt();
        Max = (int) Math.pow(10, K);

        notSosu = new boolean[Max]; // true면 소수 아님 false면 소수임
        sosuSum = new boolean[Max]; // true면 서로 다른 소수 합임
        sosuMult = new boolean[Max]; // true면 소수 곱임

        nums = new int[K];
        visited = new boolean[10];
        answer = 0;
        eratos();
        makeSum();
        makeMult();

        perm(0, 0); // 순열
        System.out.println(answer);
    }

    // 에라토스테네스의 체
    private static void eratos() {
        notSosu[0] = true;
        notSosu[1] = true;
        for (int i = 2; i < Max; i++) {
            if (notSosu[i]) {
                continue;
            } else {
                for (int j = i + i; j < Max; j += i) {
                    notSosu[j] = true;
                }
            }
        }
    }

    // 서로 다른 두 소수 합
    private static void makeSum() {
        outer:
        for (int i = 2; i < Max; i++) {
            if (notSosu[i]) continue;

            for (int j = i + 1; j < Max; j++) {
                if (notSosu[j]) continue;
                if (i + j >= Max) continue outer;
                sosuSum[i + j] = true;
            }
        }
    }

    // 두 소수 곱
    private static void makeMult() {
        outer:
        for (int i = 2; i < Max; i++) {
            if (notSosu[i]) continue;

            for (int j = i; j < Max; j++) {
                if (notSosu[j]) continue;

                // 이부분 조심 .. long 타입으로 해야한다.
                // 예를 들어 K = 5 일 때 46349*46349=2148229801 => int이면 음수

                long num = (long) i * (long)j;
                if (num >= Max) continue outer;

                sosuMult[i * j] = true;
            }
        }
    }

    private static void perm(int cnt, int num) {
        if (cnt == K) {
            // 기저조건
            if (sosuSum[num]) {
                while (true) {
                    if (num % M == 0) { // 나누어떨어지면
                        num /= M;
                    } else {
                        break;
                    }
                }
                if (sosuMult[num]) {
                    answer++;
                }
            }
            return;
        }

        for (int i = 0; i < 10; i++) {
            if (cnt == K - 1 && i == 0) continue; // 수의 맨 앞에는 0이 올 수 없다.

            if (visited[i]) continue;

            visited[i] = true;
            nums[cnt] = i;
            perm(cnt + 1, num + i * (int)Math.pow(10,cnt));
            visited[i] = false;
        }
    }
}

 

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

22943번: 수

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4#/media/%ED%8C%8C%EC%9D%BC:Sieve_of_Eratosthenes_animation.gif

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전