[Java] 백준 1644번 소수의 연속합 952hi의 접근방법

1. 문제접근

 

1)2이상 N이하 소수를 구해야 합을 구할 수 있겠다.

소수를 구하려면 에라토스테네스의 체를 사용해야겠다고 생각이 바로 들었다.

에라토스테네스의 체를 간단하게 설명하자면

2부터 N의 제곱근까지 범위에서 체크하지않은 수가 들어오면 소수로 판단하고

소수의 배수 전부를 체크배열에서 체크해 다음 소수판단에서 삭제하는 알고리즘이다 

시간복잡도가 O(N/2)으로 굉장히 빠르다.

  

2)구한 소수를 연속으로 합쳐 주어진 N을 만들 수 있는지 판단해야겠다.

구한 소수 체크배열을 통해 체크안된 값은 소수이므로 리스트로 구현해 N이 굉장히 클때 탐색시간을 줄여야겠다고 생각했고

슬라이딩윈도우방식으로 매번 소수의 합을 구하고 N보다 작으면 윈도우 크기를 크게만들고 N보다 커지면 중지시켰다.

 

2. 느낀점

 

처음에 목표값이 400000이라 햇을때 모두 체크배열로 받아도 터지지않을까 라고생각하고 계산은 안하고

그냥 그때그때 계산하면 되겠지 라고 생각해서 괜히 고생했다.

메모리계산좀 해라..

 

3. 코드

 

import java.io.*;
import java.util.ArrayList;
public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 목표 수 입력
		boolean[] prime = new boolean[N+1]; // 체크배열 생성
		ArrayList<Integer> list = new ArrayList<Integer>(); // 소수를 담을 리스트 생성
		prime[0] = true; // 0과 1은 소수가 아님 
		prime[1] = true; // 소수는 1보다 큰 자연수 중 약수가 1과 자기 자신인 수
		int max = (int) Math.sqrt(N); // 제곱근을 통해 가장큰 소수 범위지정
		for(int i=2;i<=max;i++) {
			if(!prime[i]) { // 체크안됐으면 소수 -> 소수의 배수는 모두 소수가 아님
				for(int j=i*i;j<=N;j=j+i) {
					prime[j]=true;
				}
			}
		}
		for(int i=2;i<=N;i++) { // 체크안된부분은 리스트로 관리
			if(!prime[i]) list.add(i);
		}
		int size = list.size(); // 최대 크기를 반복문안에서 받으면 계속 실행되므로 밖에서 구함
		int res = 0; // 정답 변수
		for(int i=0;i<size;i++) { // 소수의 개수만큼 반복
			int sum = list.get(i);
			if(sum==N) { // 합이 목표값이면 증가시키고 종료
				res++;
				break;
			}
			for(int j=i+1;j<size;j++) {
				sum += list.get(j); // I~J까지 합을 구함
				if(sum==N) { // 구한 합을 바탕으로 같으면 다음 소수로
					res++;
					break;
				}else if(sum>N) break; // 크면 다음 소수로 이동
			}
		}
		System.out.println(res);
	}
}

 

4. 시간 및 메모리

 

 

다른 사람들이 작성한 코드랑 크게 다른부분이 없는것 같은데 40~50 정도 더 많이 나와서 수정해보려했으나 실패