[boj6884/Java] 소수 부분 수열

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

6884번: 소수 부분 수열

문제 풀면서 연속 부분 수열이라는걸 놓치고 있어서 조합으로 풀어야하는건가 하고 계속 고민했는데, 연속 부분 수열이여서 삽질을..

 

문제를 풀면서 수를 계속 소수인지 아닌지 확인해봐야할 것 같아서 모든 원소를 다 더한 값까지 에라토스테네스의 체를 미리 만들고 부분합을 길이를 기준으로 탐색을 하려고 했다. (지금 생각해보니 범위가 그렇게 넓지 않고, 소수 부분 수열을 찾으면 프로그램을 멈추기 때문에, 에라토스테네스의 체를 만드는 것 보다 prime인지 아닌지를 그때그때 체크하는게 더 빠를 것 같다. 그리고 에라토스테네스의 체를 만들면 메모리도 많이 잡아먹음.. 만약 모든 부분 수열을 찾는 경우였으면 에라토스테네스의 체가 빨랐을지도..?)

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			int arr[] = new int[n];
			int prefix[] = new int[n+1];
			int sum = 0;
			boolean flag = false;
			prefix[0]=0;
			for(int i = 0; i<n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
				sum += arr[i];
				prefix[i+1] = prefix[i]+arr[i];
			}
			
			//소수 판별 배열 만들기(에라토스테네스의 체)
			// 소수이면 0이 아님.
			int [] isPrime = new int[sum+1];
			for(int i = 2; i<=sum; i++) {
				isPrime[i] = i;
			}
			for(int i = 2; i<=Math.sqrt(sum); i++) {
				if(isPrime[i] != 0) {
					for(int j = i*2; j<=sum; j+=i) {
						isPrime[j] = 0;
					}
				}
			}
			
            //길이가 2일때부터 n까지 먼저 길이가 2인 모든 연속 부분 수열을 살펴보고
            //그 다음 길이를 갖는 수열을 찾는다.
			for(int i = 2; i<=n; i++) {
           		//제일 앞에서부터 시작해서 수열을 탐색
				for(int j = 0; j<=n-i; j++) {
					if(isPrime[prefix[j+i]-prefix[j]] != 0) {
						sb.append("Shortest primed subsequence is length ").append(i).append(":");
						for(int k = j; k<j+i; k++) {
							sb.append(" ").append(arr[k]);
						}
						sb.append('\n');
						flag = true;
						break;
					}
				}
				if(flag) {
					break;
				}
			}
			if(!flag) {				
				sb.append("This sequence is anti-primed.\n");
			}
		}
		
		System.out.print(sb);

	}

}

-> 코드 수정할 수 있는 부분

1. 에라토스테네스의 체를 그대로 사용할 것이라면 int가 아니라 boolean을 사용해서 메모리 사용량을 줄일 수 있다.

2. 에라토스테네스의 체 대신에 소수 판별 함수를 만들어 처리할 수 있다.