[백준 알고리즘] 백준 1644번 소수의 연속합 자바(Java)
문제
하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
- 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.
풀이
1. 2부터 자연수 N사이의 소수들을 구하는 배열을 생성(decimalList[]), 이때 에라토스테네스의 체 사용
※혹시라도 에라토스테네스의 체를 모르신다면 다른 블로그에서 이해하시고 오시는걸 추천드립니다. 아직
저의 블로그에는 에라토스테네스의 체 설명 관련 글이 없습니다ㅠㅠ -> 추가할예정
2. 반복문을 통해 sum += decimalList[i] 를 해줌으로써 sum이 자연수 N과 같거나 클때까지 더해준다.
3. 자연수 N과 같게되면 소수의 연속합의 경우가 나온것이므로 count++; 시켜준다.
4. 3번과 반대로 자연수 N보다 연속합이 높은 경우 다시 반복문을 돌려준다.(i++ 시켜준후 다시 sum+decimalList[i])
5. 더 시간복잡도를 알려주는 방법을 생각해보면 3,4번을 진행하고 다음 반복문을 진행하기 전에
그 전에 사용했던 소수들의 합을 이용해준다. 밑에 그림을 통해 설명하겠지만 간략하게 얘기하자면
숫자 21이 주어지고 sum = 2+3+5+7+9 > 21이 되므로 다시 sum = 3부터 시작할거다
하지만 처음과 끝을 제외한 소수의 합 3+5+7을 활용하여 sum= 3+5+7 -> sum = 3+5+7+9 식으로 진행되게한다
예제 입력 예시
41
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
//이중반복문 -> 루트(Math.sqrt)사용 ->에라토스테네스의 체를 사용하면 시간복잡도가 더 준다
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());
boolean prime[] = new boolean[N+1]; //N까지의 모든 수를 prime에 대입
ArrayList<Integer> decimal_list = new ArrayList<>(); //정수 N보다 낮은 소수들의 모음집
prime[0] = prime[1] = true;
for(int i = 2; i*i<=N; i++)
{
if(!prime[i]) //prime[i]가 소수라면 false 아니면 true
{
for(int j = i*i; j<=N; j+=i) //j의 배수들을 제거
{
prime[j] = true;
}
}
}
for(int i = 1; i<=N; i++)
{
if(!prime[i])
{
decimal_list.add(i);
}
}
//여기부터가 시작 소수의 합이 되는 경우가 몇개인지 찾기
int count = 0; //소수들의 합으로 되는 경우의 수
int sum = 0; //연속된 소수의 합
int front = 0;
for(int i = 0; i< decimal_list.size(); i++) //소수들 한번씩 돌려서 확인해보기
{
for(int j = i; j < decimal_list.size(); j++) //연속된 소수의 합이 N과 같은지 아니면 그값을 넘어버리면 초기화 해버리기
{
sum += decimal_list.get(j);
if(sum == N) //연속된 소수의 합이 N과 같은 경우
{
count++;
sum = sum - decimal_list.get(front) - decimal_list.get(j); //지금 sum은 맨앞과 맨뒷값을 뺀상태
i = j-1; //방금 decimal_list(j)값부터 다시 sum에 더해주기 위해서 i를 j까지 올린다
front++;
break;
}
else if(sum > N) //연속된 소수의 합이 N을 초과할경우
{
sum = sum - decimal_list.get(front) - decimal_list.get(j); //지금 sum은 맨앞과 맨뒷값을 뺀상태
i = j-1; //방금 decimal_list(j)값부터 다시 sum에 더해주기 위해서 i를 j까지 올린다
front++;
break;
}
}
}
System.out.println(count);
}
}
문제 출처
https://www.acmicpc.net/problem/1644
1644번: 소수의 연속합
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)
www.acmicpc.net