1644번 문제

문제

풀이

처음 문제를 읽었을 땐 '이걸 어케 구해 ..' 싶었는데,
내가 정리해놓은 에라토스테네스의 체 글을 다시 읽어보고 나니 로직이 쉽게 생각났다.

1. n보다 작은 소수들을 찾아 수열을 구성한다. (오름차순)
2. 투포인터로 합이 n이 되는 부분수열을 구한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] primeArr = getPrimesLessThan(n);
    
        int s=0, e=0;
        int curSum = primeArr.length == 0? 0 : primeArr[0];
        int cnt = 0;
        while(s<primeArr.length) {
            if(curSum == n) {
                cnt++;
                curSum-=primeArr[s];
                s++;
            } else if(curSum > n) {
                curSum-=primeArr[s];
                s++;
            } else {
                if(e>=primeArr.length-1) {
                    curSum-=primeArr[s];
                    s++;
                } else {
                    e++;
                    curSum+=primeArr[e];
                }
            }
        }
        bw.write(cnt+"");
        bw.flush();
        bw.close();
    }

    static int[] getPrimesLessThan(int n) {
        if(n==1) return new int[0];
        boolean[] prime = new boolean[n+1];
        int size = n-1;
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;

        for(int i=2; i*i<=n; i++) {
            if(!prime[i]) continue;
            for(int j=i*i; j<=n; j+=i) {
                if(prime[j]) {
                    prime[j] = false;
                    size--;
                }
            }
        }

        int[] result = new int[size];
        int idx = 0;
        for(int i=2; i<=n; i++) {
            if(prime[i]) result[idx++] = i;
        }
        return result;
    }
}

getPrimesLessThan 메서드의 경우

• 에라토스테네스의 체 알고리즘 사용
• n = 1일 경우 처리
• n보다 작은 소수의 개수를 int size 변수로 나타냄
  → 1~n 에서 1은 소수가 아니므로 n-1로 초기화
  → 이후 for문에서 prime이 아님을 확인할 때마다 size--;
• prime[i]의 값이 true인 i만 배열에 저장하여 리턴

번외

BufferedWriter의 write()를 사용할 때, 안에 int 형 정수를 넣으면 원하는 값을 얻지 못 한다.
이는 BufferedWriter가 문자기반의 보조스트림이기 때문이다.
따라서 String이 아닌 다른 변수를 String으로 변환하여 넣어주어야 원하는 값을 출력할 수 있다.

---