boj 1644

문제 풀이

1. 소수를 구한다.
2. 투포인터를 이용하여 연속된 길이의 합을 구하며 해당 값이 될때 count +1한다

즉 이 문제는 소수구하기 에라토스테네스의 체 와 투포인터로 풀 수 있는 문제이다

에라토스테네스의 체

소구 구하기 문제이다

boolean[] visited = new boolean[n+1];

for(int i=0; i<=n; i++){
	visited[i] = true;
    
}

visted[0] = false;
visited[1] = false;
for(int i=2; i<=Math.sqrt(n); i++){
           for (int j = i * i; j <= n; j += i) {
                    is[j] = false;
            }
        }

즉 j를 i*i 로 하여 +i 씩 돌려줘 소수를 false 지우는 것이다

그 후 나는 list를 활용하여 visited 가 true (소수) 인것을 담았다.

투포인터

투포인터는

https://velog.io/@limjongheok/boj-1806
해당 부분합 문제와 같다

1. start end 를 0 0으로 지정하고
2. 처음 sum 은 list.get(0)
3. start <= end 일때
4. 만약 sum 이 n보다 작으면 end ++ sum +end ;
5. 만약 sum 이 n 보다 크거나 같다면 sum - end start ++
6. 만약 sum 이 같으면 count 올려주기
7. 만약 end 가 끝까지 같을때 sum 이 n 보다 작으면 break( 작다는것은 더이상 움직일 수 없다는 것이기때문)

//1. 
int  start = 0;
int end = 0;

//2.
int sum = list.get(0)

//3. 
while(start<=end){
	//4.
    if(sum < n){
    	end++;
        sum = sum+list.get(end);
    }else if(sum >=n) {//5.
    	// 6.if(sum == n){
        	count ++;
        }
    	sum = sum - list.get(start);
    }
    
    //7.
    if(end == n-1){// 끝까지 같을때 
    	if(sum < n){
        	break;
        }
    }

}

그래서 이 두 식을 합치면 답이 나오는줄 알았지만

90% 정도에서 IndexOutOfBounds 에 걸린것이다.

찾아보니 1일시 소수가 안만들어져 list의 사이즈 가 0이여 list.get(0) 부분에서 위와같은 런타임 에러가 발생하는 것

그래서

if(list.size()==0){
	System.out.println(0);
}else{
	// 투포인터 
}

위와 같이 바꾸었다.

전체 코드

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

        int n = Integer.parseInt(br.readLine());

        boolean[] is = new boolean[n+1];
        for(int i=0; i<is.length; i++){
            is[i] = true;
        }
        is[0] = false;
        is[1] = false;
        for(int i=2; i<=Math.sqrt(n); i++){
            for (int j = i * i; j <= n; j += i) {
                is[j] = false;
            }
        }

        List<Integer> list = new ArrayList();

        for(int i =0; i<is.length; i++){
            if(is[i]){
                list.add(i);
            }
        }
        if(list.size() == 0){
            System.out.println(0);
        }else{
            int start =0;
            int end = 0;
            int count = 0;
            int sum = list.get(0);
            while(start <= end){

                if(sum < n){
                    end  = end +1;
                    sum = sum + list.get(end);
                } else if (sum >=n) {
                    if(sum == n){
                        count++;
                    }
                    sum = sum - list.get(start);
                    start = start+1;
                }
                if(end == list.size()-1){
                    if(sum <n){
                        break;
                    }
                }

            }
            System.out.println(count);
        }




    }

성공