백준 1644 소수의 연속합 [자바]

in Develop / Solving

java

문제 분석

  • 숫자가 주어진다.
  • 이 숫자를 하나 이상의 연속된 소수의 합으로 나타낼 수 있는가.
  • 나타낼 수 있으면 그 경우의 수를 출력해라.

입력조건

숫자 N

풀이과정

  • 아리스토테네스의 체로 소수를 걸러낸 뒤,

  • 투포인터로 부분합을 구하면서 답의 수를 찾아 냄.

  • 간단하게 풀 수 있을 줄 알았지만, 생각보다 조건이 까다로웠다.

  • 우선, 아리스토테네스의 체로 소수를 걸러낼 때, 루트N 까지의 숫자까지만 확인을 진행한다.
    루트까지 보는 이유는 아리스토테네스의 체의 기본내용이므로 생략

  • 걸러진 소수를 가지고, 우리가 목표하는 수의 반을 구분자로 잡고, 그보다 작은 수들과, 구분자보다 큰 수 하나만 범위로 가져오면 된다.

    • 구분자보다 큰 수 두 개 이상을 더해면 무조건 구하려는 수보다 크기 때문이다.

  • 이렇게 가져온 수들을 이용해 투 포인터로 답을 판단한다.

  • 추가로, 입력받은 숫자가 소수일 때를 생각해 봐야 한다.

    • 숫자를 가져올 때, 목표값의 반보다 큰 것을 거의 다 생략했기 때문에, 당연히 가장 큰 수도 생략됐을 것이고, 이 수가 목표값과 같은 수일 가능성이 있다.(목표값이 소수일 때)
    • 이 경우를 판단해서 정답에 +1을 해 준다.

코드 구성

  • 아리스토테네스의 체

    int sqnum = (int) Math.sqrt(num);
for( int i = 2; i <= sqnum; i++) {
    if(a[i]) continue;
    a[i] = true;
    nums.add(i);
  
    int idf = i * i;
    while(idf <= num) {
        a[idf] = true;
        idf += i;
    }
}
int ii = sqnum+1;
while(true) {
    if(!a[ii]) {
        if( ii < num) nums.add(ii);
        if(ii > num/2)
            break;
    }
    ii++;
}

  • 투포인터

    int anscount = 0;
int l = 0;
int r = 0;
int sum = nums.get(0);
while( r < nums.size()-1 ) {
    if(sum < num) 	   sum += nums.get(++r);
    else {
        if (sum == num) anscount++;
        sum -= nums.get(l++);
    }
}
  
while(l <= r && sum >= num) {
    if(sum == num) anscount++;
    sum -= nums.get(l++);
}

전체 코드

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

public class BJ1644_소수의연속합 {
	public static void main(String[] args) throws IOException {
		int num = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
		
		boolean[] a = new boolean[num+2];
		a[1] = true;
		ArrayList<Integer> nums = new ArrayList<>();
		
		// 소수 가져오기.
		int sqnum = (int) Math.sqrt(num);
		for( int i = 2; i <= sqnum; i++) {
			if(a[i]) continue;
			a[i] = true;
			nums.add(i);
			
			int idf = i * i;
			while(idf <= num) {
				a[idf] = true;
				idf += i;
			}
		}
		int ii = sqnum+1;
		while(true) {
			if(!a[ii]) {
				if( ii < num) nums.add(ii);
				if(ii > num/2)
					break;
			}
			ii++;
		}
		
		// 투포인터
		int anscount = 0;
		if(nums.size() > 0) {
			int l = 0;
			int r = 0;
			int sum = nums.get(0);
			while( r < nums.size()-1 ) {
				if(sum < num) 	   sum += nums.get(++r);
				else {
					if (sum == num) anscount++;
					sum -= nums.get(l++);
				}
			}
			
			while(l <= r && sum >= num) {
				if(sum == num) anscount++;
				sum -= nums.get(l++);
			}
		}
		// num이 소수일 때
		if(!a[num]) anscount++;
		System.out.println(anscount);
	}
}