[백준/JAVA] 1644번: 소수의 연속합

🔺 문제

1644번: 소수의 연속합

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static boolean[] isPrime;
    static ArrayList<Integer> numbers = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        // 1. 소수 구하기
        isPrime = new boolean[N + 1];
        isPrime[0] = isPrime[1] = true;
        
        for(int i = 2 ; i <= (int)Math.sqrt(N) ; i++) {
            if(isPrime[i])  continue;
            for(int j = i * i ; j <= N ; j += i) {
                isPrime[j] = true;
            }
        }
        
        for(int i = 1 ; i <= N ; i++) {
            if(!isPrime[i])
                numbers.add(i);
        }
        
 
        // 2. 연속합으로 주어진 정수 구할 수 있는지 판별
        int start = 0, end = 0, sum = 0, cnt = 0;
        
        while(true) {
            if(sum >= N)
                sum -= numbers.get(start++);
            else if(end == numbers.size())
                break;
            else
                sum += numbers.get(end++);
            
            if(N == sum) cnt++;
        }
        System.out.println(cnt);
    }
}
 

✅ 해결 아이디어
✔ 에라토스테네스의 체 + 투 포인터
  1. 소수 구하기 → 에라토스테네스의 체 이용
  2. 소수의 연속 합으로 주어진 정수 구할 수 있는지 판단하기 → 투 포인터

- 자연수가 주어지고, 연속되었다는 점에서 투 포인터 사용 가능

 

 

💥 유의사항

• 투 포인터 움직일 때 리스트 범위 잘 지키기!

 

---

🔺 다른 풀이들

- 에라토스테네스의 체 + 투 포인터 사용하신 풀이!! 그림 짱.. 

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

---

💬 느낀 점

오왓 오랜만에 에라토스테네스의 체 풀려다 잊고....

투 포인터도 넘 오랜만이고...ㅎ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[JAVA] 백준 1644 문제 - 소수의 연속합