백준 1644; java

- 정답 코드

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

public class Main {

	static boolean prime[];
	static ArrayList<Integer> primes = new ArrayList<>();
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(bf.readLine());
		int result=0;
		int s=0, l=0, sum=0;
		//ArrayList<Integer> primes=new ArrayList<Integer>();

		prime = new boolean[N+1];        
        prime[0] = prime[1] = true;       
        for(int i=2; i*i<=N; i++){
            if(!prime[i]) for(int j=i*i; j<=N; j+=i) prime[j]=true;                
        }            
        for(int i=1; i<=N;i++){
        	if(!prime[i]) primes.add(i);     
        }

		Collections.reverse(primes);
		//System.out.println(primes);
		s=primes.size()-1; l=primes.size()-1;
		int i=l;
		while(i>=0){
			sum=sum+primes.get(i);
			//System.out.println(sum);
			if(sum > N) {
				sum=sum-primes.get(l)-primes.get(i);
				if(l-1<s) {//s==l
					l=i; s=i; 
				}else {
					l=l-1;
				}
				//System.out.println("sum >N] i="+i+" s="+s+" l="+l);
			}else if(sum == N){
				result++;
				//System.out.println("sum==N] i="+i+" s="+s+" l="+l);
				sum=sum-primes.get(l);
				s=i;
				l=l-1;
				i--;
			}else {	//sum < N
				s=i;
				i--;
			}
		}
		System.out.println(result);
	}

}

 

소수 구할 때, 그냥 간단하게 반복문으로 돌려서 prime 리스트에 넣었는데 이렇게 하면 시간 초과가 뜬다..

구글링으로 소수 구하는 부분만 따서 넣어줬더니 정답이 나왔다.

에라토스테네스의 체라는 방법이라고 한다.

 

++공부해서 추가할 것!++