[Baekjoon/JAVA] 1837번 - 암호제작

Baekjoon Online Judge

문제로 이동

 

문제

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다.

개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 주면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다.

하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기술이 발달함에 따라, 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 돌려보아 비밀 키를 쉽게 알 수 있다는 것이다.

원룡이는 주성조교님께 비밀 키를 제출하려던 바로 직전에 이 사실을 알아냈다. 그래서 두 소수 p, q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기로 하였다. 이것을 손으로 직접 구해보는 일은 매우 힘들 것이다. 당신은 원룡이를 도와 두 소수의 곱으로 이루어진 암호와 K가 주어져 있을 때, 그 암호가 좋은 암호인지 좋지 않은 암호인지 구하는 프로그램을 작성하여야 한다.

 

입력

암호 P(4 ≤ P ≤ 10100)와 K (2 ≤ K ≤ 106) 이 주어진다.

 

출력

만약에 그 암호가 좋은 암호이면 첫째 줄에 GOOD을 출력하고, 만약에 좋지 않은 암호이면 BAD와 소수 r을 공백으로 구분하여 출력하는데 r은 암호를 이루는 두 소수 중 작은 소수를 의미한다.

 

---

예제 입력	예제 출력
143 10	GOOD
77 12	BAD 7

---

풀이

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        BigInteger P = new BigInteger(in.next()); // 두 소수의 곱으로 이루어진 암호
        int K = in.nextInt(); // 두 소수의 크기 제한
        boolean check[] = new boolean[K + 1];

        int prim; // 소수
        boolean bad = false; // K보다 작은 소수로 P가 나누어 떨어지는가?

        // 소수를 찾고, 그 소수로 P를 나눠본다.
        for (prim = 2; prim < K; prim++) {
            if (check[prim]) continue;

            // prim으로 암호가 나누어지는 지 확인
            BigInteger num = new BigInteger(prim + "");
            bad = (P.mod(num).compareTo(BigInteger.ZERO) == 0);

            if (bad) break;

            // 소수가 아닌 것들을 지운다.
            for (int i = prim * 2; i < K; i += prim)
                check[i] = true;
        }

        // 출력
        if (bad)
            System.out.printf("BAD %d\n", prim);
        else
            System.out.println("GOOD");
    }
}

소수가 아닌 것들을 소수의 곱으로 찾아서 미리 제외시키는 방식으로 문제를 풀었다.

 

아래는 처음에 짰던 코드로 계속 시간초과가 발생해 실패한 것이다. 이는 소수의 곱으로 소수가 아닌 것도 제외하고, 소수도 따로 또 찾는 비효율적인 일을 하고 있었기 때문이다. 또한 check[]의 크기를 1000001로 설정해 공간을 낭비하고 있다.

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static boolean check[] = new boolean[1000001];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        BigInteger P = new BigInteger(in.next()); // 두 소수의 곱으로 이루어진 암호
        int K = in.nextInt(); // 두 소수의 크기 제한

        int prim; // 소수
        boolean bad = false; // K보다 작은 소수로 P가 나누어 떨어지는가?

        // 소수를 찾고, 그 소수로 P를 나눠본다.
        for (prim = 2; prim <= K; prim++) {
            if (check[prim]) continue;

            if(isPrim (prim)) { // i가 소수이면
                // 해당 소수로 암호가 나누어지는 지 확인
                BigInteger num = new BigInteger(prim + "");
                bad = (P.mod(num).compareTo(BigInteger.ZERO) == 0);

                // 소수가 아닌 것들을 지운다.
                for (int i = prim * 2; i < K; i += prim)
                    check[i] = true;
            }

            if (bad) break;
        }

        // 출력
        if (bad)
            System.out.printf("BAD %d\n", prim);
        else
            System.out.println("GOOD");
    }

    // n이 소수인지 확인한다.
    public static boolean isPrim (int n) {
        if (n == 2) return true;

        // n과 나누어 떨어지는 수가 있는지 확인한다.
        for (int i = 2; i < n; i++)
            if (n % i == 0 && check[i] == false)
                return false;

        return true;
    }
}