1644. 소수의 연속합

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

1644번: 소수의 연속합

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

 

입출력 조건

• 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)
• 첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

 

LOGIC

1. N이 4,000,000까지 가므로 에라토스테네스의 체를 이용하여 소수를 구함.
2. 투포인터를 사용하여 연속된 소수의 합이 N과 같은지 판별
3. N이 소수일 경우도 판별하여 경우의 수 측정

 

이 문제에서는 연속된 소수의 합으로 정답을 찾아야하기 때문에

2~N까지의 소수를 전부 찾아야 합니다.

소수를 구하는 방법은 흔히 2중 for문으로 제곱근을 사용해서 구할 수 있지만

N의 범위가 4백만까지 갈 수 있으므로 2중 for문을 이용하여 구하면 시간초과가 날 수밖에 없습니다.

 

그래서 2~N까지의 연속된 소수의 집합을 구하기위해 에라토스테네스의 체를 이용하여 구합니다.

에라토스테네스의 체는 2부터 소수를 구하지만 해당 소수의 배수들은 소수가 아닌 점을 이용하여

미리 소수가 아닌 값들을 제거합니다.

private static void getPrime() {
	boolean[] selectedPrime = new boolean[N + 1];
	
	//에라토스테네스의 체
	selectedPrime[0] = selectedPrime[1] = true;
	for(int i=2; i<=N; i++) { //소수인 2부터 N까지 검사
		if(!selectedPrime[i]) { //소수일 경우
        		arr.add(i); //arr에 추가
			for(int j=i*2; j<=N; j+=i) { //해당 소수의 배수는 모두 소수가 아니므로 true로 체크
				selectedPrime[j] = true;
			}
		}
	}
}

 

소수를 구한 다음에는 연속된 합들이 N과 같은 경우의 수를 구해야하는데

이 경우에는 투 포인터와 누적합을 사용하여 값을 구했습니다.

• 누적합이 N보다 작을 경우 오른쪽 포인터가 가리키는 수를 누적하고 포인터를 옮긴다.
• 누적합이 N보다 클 경우 왼쪽 포인터가 가리키는 수를 누적합에서 빼고 포인터를 옮긴다.
• 누적합이 N과 같을 경우 경우의 수를 증가시키고 왼쪽 포인터의 값을 빼고 포인터를 옮긴다.

while(r < size) { //오른쪽 포인터가 끝에 도달할 때 까지
	if(sum > N) { //누적합이 N보다 클 경우 왼쪽 값 빼고 포인터 옮기기
		sum -= arr.get(l++);
		
	} else if(sum < N) { //누적합이 N보다 작을 경우 오른쪽 값 더하고 포인터 옮기기
		sum += arr.get(r++);
		
	} else { //누적합과 N이 같을 경우 count 증가 후 왼쪽 값 빼고 포인터 옮기기
		count++;
		sum -= arr.get(l++);
	}
}

 

위 로직에선 arr의 마지막 값이 누적되는 순간 while문이 끝나게 되어있어서 마지막 요소가 소수인 경우의 수를 따로 검사해 줘야한다.

//마지막 소수의 값이 N과 같을 경우 count 증가
//size > 0 => N이 1일 경우
if(size > 0 && arr.get(--r) == N)
	count++;

---

CODE

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 * 백준 1644. 소수의 연속합 - 골드 3
 * @category 투 포인터, 누적합, 에라토스테네스의 체
 */
public class Main {
	static ArrayList<Integer> arr = new ArrayList<>();
	static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine()); // 연속된 소수의 합
		getPrime(); // 소수 구하기
		
		int r = 0, l = 0; //투 포인터
		int count = 0, sum = 0;
		int size = arr.size();
		
		while(r < size) { //오른쪽 포인터가 끝에 도달할 때 까지
			if(sum > N) { //누적합이 N보다 클 경우 왼쪽 값 빼고 포인터 옮기기
				sum -= arr.get(l++);
				
			} else if(sum < N) { //누적합이 N보다 작을 경우 오른쪽 값 더하고 포인터 옮기기
				sum += arr.get(r++);
				
			} else { //누적합과 N이 같을 경우 count 증가 후 왼쪽 값 빼고 포인터 옮기기
				count++;
				sum -= arr.get(l++);
			}
		}
		
		//마지막 소수의 값이 N과 같을 경우 count 증가
		//size > 0 => N이 1일 경우
		if(size > 0 && arr.get(--r) == N)
			count++;
		
		System.out.println(count);
	}

	private static void getPrime() {
		boolean[] selectedPrime = new boolean[N + 1];
		
		//에라토스테네스의 체
		selectedPrime[0] = selectedPrime[1] = true;
		for(int i=2; i<=N; i++) { //소수인 2부터 N까지 검사
			if(!selectedPrime[i]) { //소수일 경우
        			arr.add(i); //arr에 추가
				for(int j=i*2; j<=N; j+=i) { //해당 소수의 배수는 모두 소수가 아니므로 true로 체크
					selectedPrime[j] = true;
				}
			}
		}
	}
}