[Baekjoon] 1837 암호제작 - JAVA

문제

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

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

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

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

---

입력

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

---

출력

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

---

예제 입력 1 

143 10

예제 출력 1 

GOOD

예제 입력 2 

77 12

예제 출력 2 

BAD 7

---

📝 제출 답안

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        BigInteger P = new BigInteger(st.nextToken());
        BigInteger K = new BigInteger(st.nextToken());
        BigInteger r = new BigInteger("1");

        // 루프 변수 r을 1부터 시작하여 증가시키면서
        // P가 2 이상 K-1 이하의 숫자로 나누어지는지 확인
        while(true) {
            // r 값이 K 이상일 경우
            if (r.compareTo(K) == 1 || r.compareTo(K) == 0) {
                System.out.println("GOOD");
                break;
            }

            // r 값을 1만큼 증가시켜 다음 숫자 확인
            r = r.add(BigInteger.ONE);

            // P 를 r 로 나누어 떨어지고, r 이 K 보다 작을 경우
            if (P.remainder(r).compareTo(BigInteger.ZERO) == 0 && r.compareTo(K) == -1) {
                // r 은 P 의 작은 약수
                System.out.println("BAD " + r);
                break;
            }
        }

    }
}

 

 

이번 문제는 이해가 안돼서 구글링하면서 풀었다..

결론적으로 이 문제는 입력받은 두 개의 정수 P와 K를 이용해 P가 2 이상 K-1 이하의 수로 나누어지는지 판별하는 프로그램이다.

 

 

CompareTo 메서드

풀이에 앞서 compareTo() 메서드를 알고 가야한다.

compareTo(BigInteger other) 메서드는 현재 BigInteger와 other 값을 비교하여 0, 1, -1 중 하나를 반환한다.

표현식	의미
a.compareTo(b) == 0	a == b
a.compareTo(b) == -1	a < b
a.compareTo(b) == 1	a > b

 

 

입력 처리 및 변수 초기화

P의 입력 범위가 10의 100제곱까지 가능하기 때문에 BigInteger 타입으로 입력 받는다.

r은 1부터 시작하는 루프 변수로, P가 2 이상 K-1 이하의 숫자로 나누어지는지 확인하기 위해 1부터 증가하여 나눗셈을 수행한다.

 

 

무한 루프

if (r.compareTo(K) == 1 || r.compareTo(K) == 0) {
    System.out.println("GOOD");
    break;
}

 

r.compareTo(K) == 1은 r이 K보다 클 경우이고, r.compareTo(K) == 0 은 r과 K의 값이 동일할 경우이다.

즉, r이 K 이상이면 루프를 종료하고 GOOD을 출력하고 루프를 빠져나간다. P가 2 이상 K-1 이하의 어떤 수로도 나누어떨어지지 않는다는 의미이다.

 

 

r = r.add(BigInteger.ONE);

 

루프를 한 번 돌 때마다 r값을 1씩 증가시켜 다음 숫자를 저장한다.

 

 

if (P.remainder(r).compareTo(BigInteger.ZERO) == 0 && r.compareTo(K) == -1) {
    System.out.println("BAD " + r);
    break;
}

 

P.remainder(r).compareTo(BigInteger.ZERO) == 0 는 P를 r로 나누었을 때 나머지가 0이면 P가 r로 나누어 떨어진다는 것을 의미한다. r.compareTo(K) == -1 은 r이 K보다 작은지를 확인하는 것이다.

즉, P가 K보다 작은 숫자로 나누어 떨어진다면 BAD r 을 출력하고 루프를 빠져나간다.

이때 출력되는 r 값은 P(=p×q)의 작은 약수이다.

 

제출 현황