[백준 7512번] 연속하는 소수의 합

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

 

 

처음에 각각 ni개들에서 합을 구했을 때 나오는 소수 중에서 가장 작은 값을 구하라고 문제를 잘못 파악했는데, 테스트 케이스를 보니, m개의 합에 대한 소수중에서 공통인 소수의 최솟값을 구하는 문제였다.

 

문제를 정확히 파악하는게 중요하다.

 

또한 문제에서 정답은 10^7이었는데, m개의 소수의 합을 구했을 때, 소수의 합이 우선 int형의 크기를 초과할 수 있으므로 long 타입으로 선언하는게 중요하다. 그렇게 하지 않아서 ArrayIndexOutOfBoundException이 났었다.

 

소수를 구할 때, 에라토스테네스의 체를 사용하였다.

기본적인 소수를 구하는 알고리즘을 작성한다면 O(N^2)인데, 에라토스테네스의 체를 사용하면 log(NlogN)으로 구할 수 있다.

 

import java.io.*;
import java.util.*;

public class BOJ_7512_G3_연속하는소수의합 {

	static boolean[] prime;
	static List<Integer> sosu;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = null;
		StringTokenizer st = null;

		int T = Integer.parseInt(br.readLine());
		int M;

		sosu = new ArrayList<>();
		prime = new boolean[10_000_001];

		makePrime();

		int tc = 1;
		while (T-- > 0) {
			M = Integer.parseInt(br.readLine());
			sb = new StringBuilder();
			Map<Long, Integer> map = new HashMap<>();

			st = new StringTokenizer(br.readLine());

			int res = 10_000_002;
			for (int i = 0; i < M; i++) {
				// 슬라이딩 윈도우의 개수
				int N = Integer.parseInt(st.nextToken());
				long sum = 0L;

				// check 해야함.
				for (int j = 0; j < N; j++) {
					sum += sosu.get(j);
				}

				if (sum <= 10_000_000 && prime[(int)sum]) {
					map.put(sum, map.getOrDefault(sum, 0) + 1);
				}

				int idx = 0;
				while (idx + N < sosu.size()) {
					sum -= sosu.get(idx);
					sum += sosu.get(idx++ + N);

					if (sum > 10_000_000) continue;

					if (!prime[(int)sum]) continue;

					map.put(sum, map.getOrDefault(sum, 0) + 1);

					if (map.getOrDefault(sum, 0) == M) {
						sb.append("Scenario " + tc++ + ":\n");
						sb.append(sum + "\n");
						break;
					}
				}
			}


			System.out.println(sb);
		}

	}

	static void makePrime() {

		for (int i = 0; i < 10_000_001; i++) {
			prime[i] = true;
		}

		prime[0] = false;
		prime[1] = false;

		for (int i = 2; i < Math.sqrt(10_000_001); i++) {

			if (prime[i]) {
				for (int j = i * i; j < 10_000_001; j+= i) {
					prime[j] = false;
				}
			}
		}

		for (int i = 0; i < 10_000_001; i++) {
			if (prime[i]) sosu.add(i);
		}
	}
}