[백준] 1644번 소수의 연속합 JAVA 풀이
나의 풀이
소수인지 아닌지 매번 확인하면 시간초과가 반드시 날것이라 생각해서 '에라토스테네스의 체'를 활용해 list에 4백만까지의 숫자 중에서 소수만을 넣어주었다.
그 이후에는 단순히 투포인터를 활용해서 더해줬는데, 내가 실수했던 부분이 left와 right의 시작점이 둘 다 0이었어야 했는데 left = 0, right = 1부터 시작하게 해서 97%에서 자꾸 틀리는 바람에 시간이 조금 더 걸렸다.
문제를 봤을 때, 연속적인 숫자들의 합이면 누적합을 써서
right에 해당하는 누적합 - left에 해당하는 누적합
과 같이 시간 복잡도를 더 줄일 수 있다는 생각을 했다.
그러나
- 누적합 알고리즘을 구현하는데도 어느정도 시간이 소요되고
- 1부터 4백만까지의 소수의 개수도 40만개 가량밖에 되지 않으며
- 투포인터를 활용하게되면 left가 right를 넘어가는 경우 등에서 break를 사용하면 되고
- 마지막으로 2초의 시간제한 문제이므로
단순하게 문제를 풀었다!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
class Main {
static boolean prime[] = new boolean[4_000_001];
static List<Integer> prime_list = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
prime();
int size = prime_list.size();
int count = 0;
int left = 0;
int right = 0;
while (true) {
int sum = sum(left, right);
if (sum == N) {
count += 1;
right += 1;
} else if (sum < N) {
right += 1;
} else {
left += 1;
}
if (right == size || left == size || left > right) {
break;
}
}
System.out.println(count);
}
static void prime() {
int n = 4000000;
// 소수가 아니면 true
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 = 0; i < 4000001; i++) {
if (!prime[i]) {
prime_list.add(i);
}
}
}
static int sum(int start, int end) {
int sum = 0;
for (int i = start; i <= end; i++) {
sum += prime_list.get(i);
}
return sum;
}
}
Author And Source
이 문제에 관하여([백준] 1644번 소수의 연속합 JAVA 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hahahaa8642/백준-1644번-소수의-연속합-JAVA-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)