[백준 1837번] 암호 제작 (브루트 포스, 완전 탐색, Java)

 

문제설명

입력 & 출력

나의 풀이

이번 문제는 문제 1837번 (암호제작)은 소수와 나머지 연산을 활용하여 암호를 제작하는 문제입니다.

소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 돌려보아 비밀 키를 쉽게 알 수 있다는 것이다.

 

문제 설명에서 나와 있듯이 위 문구처럼 "모든 경우의 수를 돌려보면 == 브루트 포스 "입니다.

 

 

따라서  두 소수 p, q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 좋지 않은 암호면 "BAD"와 소수를 출력하고, 좋은 암호면 "GOOD"을 출력하는 문제입니다.

 

 

풀이를 설명하자면, 먼저 다음과 같은 순서로 문제를 풀이했습니다.

 

• 1. 소수인지 확인
  • 소수 ➡️ P를 해당 소수로 나눈 나머지(mod)가 0이라면 "BAD"와 해당 소수를 출력하고 그 즉시 반복문을 종료한다. (다른 소수는 비교할 필요가 없기 때문)
  • 소수 X ➡️ 나누어떨어지지 않으면 해당 소수는 무시하고, 그 다음 소수로 넘어간다.
• 2. 모든 소수를 비교 후
  • 만약, 2부터 K−1까지의 모든 소수에 대해 나누어떨어지지 않았다면 "GOOD"을 출력한다.

 

이 때 BigInteger 클래스는 기본적으로 long, int와 같은 기본 데이터 타입을 입력으로 받을 수 없기 때문에, 숫자 값을 BigInteger로 변환하려면 명시적으로 변환해야합니다.