[백준 알고리즘] 백준 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

 

i = 2일때 소수의 연속합을 진행하면 2+3+5+7+11+13 = 41과 같게되므로 count++해준다

이후 2+3+5+7+11+13 중 처음과 끝을 제외한 3+5+7+11을 살려서 반복문을 진행한다(+ 13 + 15 하는식으로)

반복을 하다보면 결국 41은 2+3+5+7+11+13 = 11+13+17 = 41 총 3가지의 소수의 연속합이 나오는 것을 알 수 있다

소스코드

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번: 소수의 연속합