문제
레벨: G3
알고리즘: 투 포인터 + 에스토라테네스의 체
풀이시간: 1시간
힌트 참조 유무: 유
https://www.acmicpc.net/problem/1644
1 번째 시도 : 시간초과
[코드 설명]
1. arr배열에 N이하의 소수들을 담는다.
2. 소수들을 순회하며 while문 안의 내용을 반복한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int count = 0;
int start = 0;
int end = 0;
int now = 1;
int sum = 0;
int input = 0;
int[] arr = new int[N + 1];
if (isSosu(N))
count++;
int a = 0;
for (int i = 1; i <= N; i++) {
if (isSosu(i)) {
arr[a] = i;
a++;
}
}
// for (int i =0; i < N; i++) {
// System.out.println(arr[i]);
// }
while (arr[start] < (N / 2 + 1)) {
if (sum <= N) {
sum += arr[end];
end++;
} else if (sum > N) {
sum -= arr[start];
start++;
}
if (sum == N) {
count++;
}
//
// System.out.println(start);
// System.out.println(end);
// System.out.println(arr[start]);
// System.out.println(arr[end]);
// System.out.println(sum);
// System.out.println(count);
// System.out.println();
}
System.out.println(count);
}
public static boolean isSosu(int n) {
if (n == 1) {
return false;
}
int count = 0;
for (int i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
count++;
}
}
if (count == 1)
return true;
else {
return false;
}
}
}
2 번째 시도: 성공
[놓쳤던 개념]
에스토라테네스의 체
[부족한 개념]
투 포인터 종료조건
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int count = 0;
int start = 0;
int end = 0;
int sum = 0;
boolean[] prime = new boolean[N + 1];
ArrayList<Integer> primeNumbers = new ArrayList<>();
// 소수 판별을 위한 에라토스테네스의 체
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 = 2; i <= N; i++) {
if (!prime[i]) {
primeNumbers.add(i);
}
}
// 소수의 연속합을 찾기 위한 투 포인터 알고리즘
while (true) {
if (sum >= N) {
sum -= primeNumbers.get(start++);
} else if (end == primeNumbers.size()) {
break;
} else {
sum += primeNumbers.get(end++);
}
if (sum == N) {
count++;
}
}
System.out.println(count);
}
}
'알고리즘 > 투포인터' 카테고리의 다른 글
[백준 2407] 두 용액 / 자바 / 투 포인터 (0) | 2024.06.17 |
---|---|
[백준 11728] 배열 합치기 / 자바 /투 포인터 (1) | 2024.06.14 |