[코테] 백준 1837번 : 암호제작 (java)

https://www.acmicpc.net/problem/1837

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

❓문제

---

🔅해석

K까지의 소수배열을 만들기 위해  '에라토스테네스의 체'를 활용한다.

에라토스테네스의 체의 진행 과정

//에라토스테네스의 체 생성
for (int i = 2; i < K; i++) {
    if (!checked[i]) {
        primes.add(i);
        for (int j = i; j < K; j += i) {	//i의 배수 탐색
            checked[j] = true;
        }
    }
}

 

이중 for문을 돌면서 자신의 배수에 방문 체크를 하여 지워준다.

 

 

해당 소수에 암호가 떨어진다면 K보다 작은 소수로 만들어진 암호이므로 소수 배열을 돌면서 입력받은 암호를 나눠본다.

주의할 점은, 암호가 10의 100승까지 입력될 수 있어 int, long으로 입력받을 수 없다.

BigInteger를 사용하는 방법도 있지만, String으로 입력받아 한 글자씩 연산을 진행하는 방법도 있다.

(어떤 문제에는 BigInteger 사용이 불가하여 String으로 연산하는 방법도 알아야한다.)

/암호 P가 10의 100승까지 입력되기에 일반적인 연산이 어려워, 한 글자씩 연산을 진행한다.
static boolean checkIsBad(int x) {
    int r = 0;

    //몫은 저장할 필요없음
    for (int i = 0; i < P.length; i++) {
        r = (r * 10 + (P[i] - '0')) % x;
    }

    if (r == 0)  return true;
    return false;
}

 

 

---

⭕정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int K;
	static char[] P;
	static boolean[] checked;
	static List<Integer> primes = new ArrayList<>();
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		P = st.nextToken().toCharArray();
		K = Integer.parseInt(st.nextToken());
		
		checked = new boolean[K + 1];
		
		//에라토스테네스의 체 생성
		for (int i = 2; i < K; i++) {
			if (!checked[i]) {
				primes.add(i);
				for (int j = i; j < K; j += i) {	//i의 배수 탐색
					checked[j] = true;
				}
			}
		}
		
		System.out.println(primes.toString());

		boolean isGood = true;
		for (int prime : primes) {
			if (checkIsBad(prime)) {
				//나쁜 암호
				sb.append("BAD ").append(prime);
				isGood = false;
				break;
			}
		}
		if (isGood) sb.append("GOOD");
		System.out.println(sb.toString());
		br.close();
		
	}
	
	//암호 P가 10의 100승까지 입력되기에 일반적인 연산이 어려워, 한 글자씩 연산을 진행한다.
	static boolean checkIsBad(int x) {
		int r = 0;
		
		//몫은 저장할 필요없음
		for (int i = 0; i < P.length; i++) {
			r = (r * 10 + (P[i] - '0')) % x;
		}
		
		if (r == 0)  return true;
		return false;
	}
}

 

---

❗결과