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

 

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

1644번: 소수의 연속합

 

난이도 : 골드 3

 

문제를 직관적으로 바라보고 풀었는데 바로 통과가 됐습니다.

난이도보다 매우 쉬운 문제였습니다.

입력값까지의 소수를 구한 후 투 포인터로 입력된 값이 맞는지 확인해 주면 됩니다.

 

투 포인터란?

투 포인터는 2중 for문에서 변수인 i, j로 배열을 탐색하며 범위를 조절하는 방법입니다.

위의 그림에서는 i, j로 배열을 탐색 중인 모습입니다.

---

전역 변수 

n = 문제에서 주어지는 값

answer = 소수의 합이 입력 값이 되는 경우

nPrime[] = true(소수가 아님), false(소수임)

al = nPrime에서 소수만 가져온 list

메소드

void main 

입력 값을 받고 답을 출력합니다.(primeNumber, solve 호출)

void primeNumber

입력 값까지의 소수를 구합니다. 구한 소수는 ArrayList인 al에 추가합니다.

void solve

i와 j의 투 포인터로 범위를 지정하고 범위 합을 구한 후 입력값과 비교하여 answer에 반영합니다.

 

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

public class Main {
	static int n, answer;
	static boolean nPrime[];
	static ArrayList<Integer> al = new ArrayList<Integer>();
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		answer = 0;
		nPrime = new boolean[n+1];
		
		primeNumber();
		solve();
		System.out.println(answer);
	}
	
	public static void primeNumber() {
		for(int i = 2; i <= (n+1)/2; i++) {
			for(int j = 2; j*i <= n; j++)
				nPrime[j*i] = true;
		}
		nPrime[1] = true; 
		
		for(int i = 2; i <= n; i++)
			if(!nPrime[i])
				al.add(i);
	}
	
	public static void solve() {
		int sum;
		for(int i = 0; i < al.size(); i++) {
			sum = 0;
			for(int j = 0; j+i < al.size(); j++) {
				sum += al.get(i+j);
				if(sum == n) {
					answer++;
					break;
				}
				else if(sum > n)
					break;
			}
		}
	}

}