[25.03.11] 소수의 연속합

개인적으로 재밌는 문제였다.

 

아리스토테네스의 체를 이용한 소수판별 + 투 포인터 

2개를 섞으면 풀 수 있는 문제였다.

 

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int size =0;
        boolean[] prime = new boolean[n+1];
        for(int i=2; i<=n; i++){
            prime[i]=true;
        }
        prime[1] = false;
        //아리스토테네스의 체 
        for(int i=2; i<=n; i++){
            for(int j=2; j*i<=n ; j++){
                if(prime[i*j]){
                    prime[i*j]=false;
                }
            }
        }
        //소수만 따로 배열에 담기 위한 크기 
        for(int i=2; i<=n; i++){
            if(prime[i]){
                size++;
            }
        }

        int[] primeArr = new int[size];
        int index =0;
        //소수 배열 초기화
        for(int i=2; i<=n; i++){
            if(prime[i]){
                primeArr[index++]=i;
            }
        }

		//n=1일때 초기화
        if(n==1){
            System.out.printf("%d",0);
            return;
        }

        int end =0;
        int start =0;
        int sum = 2;
        int count =0;
        while(start<size && end<size){
            if(sum>n){
                if(start+1<size){
                    sum-=primeArr[start];
                    start++;
                }
                else{
                    break;
                }
            }
            else if(sum<n){
                if(end+1<size){
                    end++;
                    sum+=primeArr[end];
                }
                else{
                    break;
                }
            }
            else{
                count++;
                if(end+1<size){
                    sum+=primeArr[++end];   
                }
                else{
                    break;
                }
            }
        }
        System.out.printf("%d",count);
    }

}

 

그때그때 안되는걸 하나씩 예외처리하고 추가하고 이러다보니까 상당히 복잡해진 내 코드다.

 

마지막 부분의 더하여 소수가 되는지 판단하는 투포인터 부분만 본다면

sum=2 인 상황에서 목표 값인 n과 sum을 비교

n>sum 이면

sum을 키워야되니까 end를 오른쪽으로 옮김으로서 소수 부분수열을 확장시킨다.

n<sum 이면

sum을 줄여야되니까 start를 오른쪽으로 옮김으로서 소수 부분 수열을 축소시킨다.

n==sum 이면

count를 하나 올리고

end++ 이후 다시 sum을 업데이트 시켜준다.

 

저렇게 계속 와리가리 치다가 end나 start가 배열 밖으로 빠져나가는 순간 멈추고 count한 것을 출력하면 된다.

 

이 뇌피셜까지 세우고 코드를 짜던 와중 문제가 생겼다.

 

문제

1) 투포인터에서 같다면 end를 오른쪽으로 옮길 것인가, start를 오른쪽으로 옮길것인가, end와 start 둘 다 옮길 것인가

2) 투포인터의 반복은 어떤 조건에서 끝낼것인가? 

3) end++ 이나 start++를 하는 와중에 end++ , start++ 한 결과가 ArrayIndex 예외가 터지지 않을려면 깔끔하게 어떻게 해야될까 

 

해답

1) 상관은 없는 것 같다. 일반적으로는 나처럼 sum < n , sum > n , sum==n로 나누기보다는 그냥 sum>=n , sum<n으로 나누고 sum>=n 안에서 start를 하나 옮기는 걸로 많이 쓰는것으로 보인다. 

2)  start<end && end < size , 혹은 나처럼 그냥 start < size , end<size 해도 되기는 하는데 조기종료 + 가독성을 위해 전자가 나은것 같다.  

3) 이건 신박했는데 사람들이 나처럼 2에서 부터 하지 않고 0부터 하고 미리 앞으로 땡겨놨다가 조건문에서 땡겨놓은 걸 더하고 ++ 해주는 방식이었다. 이러면 ++ 이후에 다시 최상위 while문을 타니까 end<size 나 start<end 에서 걸릴 것이다. 

즉 현재 인덱스보다 미리 한칸 앞으로 보내놓고 계산하는 것이다.

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

class Main {
    static ArrayList<Integer> arr = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        arr.add(2);
        for (int i = 3; i <= N; i++) {
            isPrime(i);
        }
        int arrSize = arr.size();
        int left = 0,right = 0,sum = 0,cnt =0;
        while (true) {
            if (sum >= N) {
                sum -= arr.get(left++);
            }else if(right == arrSize) break;
            else{
                sum += arr.get(right++);
            }
            if (sum == N) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
    static void isPrime(int x) {
        for (int i = 2; i <= Math.sqrt(x); i++) {
            if (x % i == 0) {
                return;
            }
        }
        arr.add(x);
    }
}
출처: https://nomoreft.tistory.com/102 [개인용 뇌 도서관:티스토리]