728x90
[Gold III] 소수의 연속합 - 1644
성능 요약
메모리: 32812 KB, 시간: 176 ms
분류
수학(math), 정수론(number_theory), 소수 판정(primality_test), 에라토스테네스의 체(sieve), 두 포인터(two_pointer)
문제 설명
하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
- 3 : 3 (한 가지)
- 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
- 53 : 5+7+11+13+17 = 53 (두 가지)
하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.
자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)
출력
첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.
풀이
이 문제도 투포인터를 사용하여 풀었다
에라토스테네스의 체 : https://code-master-s.tistory.com/31
먼저 에라토스테네스의 체를 이용하여 소수를 구하고, 투포인터로 index를 조정하며 합이 N인 경우 cnt를 1씩 더하였다
합이 N 이상인 경우에 start를 1 증가, N 미만인 경우에는 end를 1 증가하였다
package BOJ.Gold.g4;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_1806_부분합 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int S = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] arr = new int[N+1]; // 누적합 저장
for (int i=1; i<=N; i++)
arr[i] = arr[i-1]+Integer.parseInt(st.nextToken());
// 투포인터
int start = 1;
int end = 1;
int ans = 100001;
while (start<=end && end<=N) { // 종료 조건 : 배열의 끝까지 훑은 경우
int sum = arr[end]-arr[start-1]; // start~end까지의 누적합
if (sum>=S) {
ans= Math.min(ans, end-start+1); // sum이 S 이상인 경우 길이 update
start++; // start를 증가시켜 더 작은 길이가 가능한지 검사
}
else end++; // sum이 S 미만인 경우 end++
}
if (ans==100001) ans=0;
System.out.println(ans);
}
}
728x90
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 1202 - 보석 도둑 (자바 Java) (0) | 2022.11.07 |
---|---|
[백준] 16946 - 벽 부수고 이동하기 4 (자바 Java) (0) | 2022.11.01 |
[백준] 1806 - 부분합 (자바 Java) (0) | 2022.10.30 |
[백준] 1987 - 알파벳 (자바 Java) (0) | 2022.10.28 |
[백준] 17143 - 낚시왕 (자바 Java) (0) | 2022.10.26 |