[백준] 좋은 암호 - 2061번

좋은 암호

2 초	128 MB	4499	1828	1582	45.604%

문제

암호화 방식 중에는 소수를 이용하는 것들이 많다. 보통은 매우 큰 두 개의 소수를 선택하고, 두 소수를 곱한 값을 암호화에서의 키로 사용하고는 한다. 이러한 방법이 좋은 이유는 일반적으로 매우 큰 수를 소인수분해 하는 것이 어렵기 때문이다.

소수를 택할 때 큰 수를 택하면, 이 둘을 곱해서 얻어지는 키 값도 커지게 된다. 하지만 그 반대는 성립하지 않을 수도 있다. 즉, 키 값이 매우 큰 경우에도 이를 소인수분해 하는 것은 쉬울 수도 있다.

따라서 암호문이 크랙되지 않도록 하기 위해서는, 키 값이 적절히 큰 수들의 곱으로 이루어져 있는지를 확인해야 할 필요가 있다. 키 값 K와 정수 L이 주어졌을 때, K를 인수분해 했을 때, 항상 L 이상의 값으로만 이루어져 있는지를 확인하고 싶다. 물론 인수분해 할 때 1로 나누는 경우는 고려하지 않는다.

예를 들어 K=143인 경우, 이는 11과 13의 곱으로 이루어져 있다. 즉, 이를 인수분해 하는 방법은 11×13, 143의 두 가지 경우뿐이다. 따라서 L이 11일 경우에는 인수분해 했을 때 나온 수들이 모두 L 이상이므로 좋은 경우지만, L이 12이상일 경우에는 좋은 암호가 아니다.

K와 L이 주어졌을 때, 좋은 암호인지 판단하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 K, L이 주어진다.

출력

좋은 암호인 경우에는 GOOD을 출력한다. 나쁜 암호일 경우에는 BAD를 출력하고, K의 가장 작은 (1 아닌) 인수를 출력한다.

제한

• 4 ≤ K ≤ 10100
• 2 ≤ L ≤ 1,000,000

예제 입력 1 복사

143 11

예제 출력 1 복사

GOOD

예제 입력 2 복사

143 12

예제 출력 2 복사

BAD 11

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 임의 정밀도 / 큰 수 연산

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 객체로 변환
        BigInteger K = new BigInteger(st.nextToken());
        BigInteger L = new BigInteger(st.nextToken());

        // L 보다 작은 인수 분해 소수를 저장할 변수 선언
        int N = 0;

        // L을 int 형으로 변환하여 i와 크기 비교 (L 값이 int 범위를 벗어나면 컴파일 오류 발생 가능성 있음)
        for (int i = 2; i < L.intValue(); i++) {
            // K를 i로 나눈 나머지가 0인지 확인
            if ((K.remainder(BigInteger.valueOf(i))).compareTo(BigInteger.ZERO) == 0) {
                N = i; // 나머지가 0이면 N에 i 값 저장
                break; // 이미 소수 인자를 찾았으니 반복문 종료
            }
        }

        // 삼항 연산자를 사용하여 N 값에 따른 S 값 결정
        String S = (N > 0) ? ("BAD " + N) : "GOOD"; // N이 0보다 크면 "BAD N", 아니면 "GOOD"


        System.out.println(S);
    }
}

 

설명:

1. 변수 선언:

int N = 0;

• 이 코드는 N이라는 이름의 변수를 선언하고 자료형을 int로 설정합니다.
• int 자료형은 정수 값을 저장하는 데 사용됩니다.
• N 변수의 초기 값은 0으로 설정됩니다.
• N 변수의 역할은 루프 과정에서 L보다 작은 소수 인수가 발견되면 해당 값을 저장하는 것입니다.

2. 소수 인수 확인 루프:

for (int i = 2; i < L.intValue(); i++) {
    // ... (코드 안에 내용)
}

• 이 for 루프는 2부터 L-1 (포함)까지 반복합니다.
• i 변수는 현재 검사 중인 잠재적 소수 인수를 나타냅니다.
• L.intValue() 표현식은 BigInteger 객체 L을 루프 내 비교를 위해 int 값으로 변환합니다.

3. i로 나누어 떨어지는지 확인:

if ((K.remainder(BigInteger.valueOf(i))).compareTo(BigInteger.ZERO) == 0) {
    N = i; // 나머지가 0이면 N에 i 값 저장
    break; // 이미 소수 인자를 찾았으니 반복문 종료
}

• 이 if 문은 K가 현재 i 값으로 나누어 떨어지는지 확인합니다.
• K.remainder(BigInteger.valueOf(i)) 표현식은 K를 i로 나눈 나머지를 계산합니다.
• compareTo(BigInteger.ZERO) 메서드는 나머지를 0과 비교합니다. 같으면 K는 i로 나누어 떨어집니다.
• K가 i로 나누어 떨어지는 경우:
  • i 값은 N 변수에 저장되어 L보다 작은 소수 인수임을 나타냅니다.
  • 소수 인수를 이미 찾았으므로 루프를 종료하기 위해 break 문을 사용합니다.

4. 출력 문자열 결정:

String S = (N > 0) ? ("BAD " + N) : "GOOD";

• 이 코드는 삼항 연산자 (? :)를 사용하여 출력 문자열 S의 값을 N 값에 따라 결정합니다.
• N이 0보다 크면 (즉, L보다 작은 소수 인수를 찾았으면) 출력 문자열은 "BAD N"이며, N은 식별된 인수입니다.
• 그렇지 않은 경우, 즉 소수 인수가 발견되지 않았다면 출력 문자열은 단순히 "GOOD"입니다.

5. 결과 출력:

System.out.println(S);

• 이 코드는 출력 문자열 S을 표준 출력 스트림에 출력합니다.
• "BAD N" 메시지는 K가 L보다 작은 소수 인수를 가지고 있음을 나타내며, N 값은 해당 인수를 나타냅니다.
• "GOOD" 메시지는 K가 L보다 작은 소수 인수를 가지고 있지 않음을 나타내므로 비교적 강력한 비밀번호임을 의미합니다.

전반적인 요약:

이 코드는 좋은암호 알고리즘을 효과적으로 구현하여 주어진 K 값이 L보다 작은 소수 인수를 가지고 있는지 확인합니다. BigInteger를 사용하여 큰 숫자를 처리하고 입력/출력 작업을 간소화합니다. 이 코드는 간결하고 이해하기 쉽으며 좋은 프로그래밍 관행을 따릅니다.