좋은 암호
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
를 사용하여 큰 숫자를 처리하고 입력/출력 작업을 간소화합니다. 이 코드는 간결하고 이해하기 쉽으며 좋은 프로그래밍 관행을 따릅니다.
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 단어나누기 - 1251번 (0) | 2024.06.12 |
---|---|
[백준] 지각 - 10419번 (1) | 2024.06.12 |
[백준] 타임머신 - 1440번 (1) | 2024.06.12 |
[백준] 블랙잭 - 2798번 (0) | 2024.06.12 |
완전탐색 & 시뮬레이션 - 1 (0) | 2024.06.12 |