[백준] 단계별로 풀어보기(단계:26, 투 포인터,JAVA)1644번, 소수의 연속합

문제 링크

1644번: 소수의 연속합

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

투 포인터는 두 가지의 위치를 가리키는 포인터 Start, End를 이용하여 1차원 배열에 저장된 값들에 범위를 더하여 해당하는 값을 구하거나 포인터가 가리키는 값을 더해서 원하는 값을 구할 수 있도록 하는 알고리즘입니다.

 

투 포인터를 사용할 때에는 주로 정렬한 상태에서 사용합니다.

이 문제에 핵심은

1. 2~N까지 연속되는 소수의 합으로 N을 만드는 경우의 수를 출력한다.

2. 각 소수는 단 한번의 덧셈만 가능합니다.

 

투 포인터 알고리즘에서는 위치를 가리키는 2가지 포인터를 설정하였습니다.

Start = 2

End = 2

 

숫자 1은 소수가 아니기 때문에 2부터 탐색을 시작하였습니다.

 

이후 저는 특성합을 오름차순으로 정렬한 뒤에 아래에 규칙대로 탐색하였습니다.

1. start ~ end 범위에 소수값의 합 > N : Start 다음 소수로 이동

2. start ~ end 범위에 소수값의 합 = N : Start 다음 소수로 이동, Count + 1

2. start ~ end 범위에 소수값의 합 < N : End 다음 소수로 이동

 

위 규칙이 나온 이유는

start ~ end 범위에 소수값의 합이 N 보다 클 때 조건에 합을 감소시켜야하기 때문에 Start + 1

 

start ~ end 범위에 소수값의 합이 N일 때 조건에 만족으로 Count + 1, 다음 만족하는 경우를 찾기 위해 Start + 1

 

start ~ end 범위에 소수값의 합이 N 보다 작을 때 조건에 합을 증가시켜야하기 때문에 End + 1

 

 

N = 5일 때

1	2	3	4	5
	Start,End

Start(2) ~ End(2) = 2(2<5)

규칙3 적용 → End 다음 소수 이동

 

1	2	3	4	5
	Start	End

Start(2) ~ End(3) = 5(5==5)

규칙2 적용 → Start 다음 소수 이동, Count + 1

 

1	2	3	4	5
		Start,End

 

Start(3) ~ End(3) = 3(3 < 5)

규칙3 적용 → End 다음 소수 이동

다음 소수는 5이기 때문에 4는 넘어갑니다.

 

1	2	3	4	5
		Start		End

 

Start(3) ~ End(5) = 8(8 > 5)

규칙1 적용 → Start 다음 소수 이동

 

1	2	3	4	5
				Start,End

 

Start(5) ~ End(5) = 5(5==5)

규칙2 적용 → Start 다음 소수 이동, Count + 1

 

다음 소수 존재하지 않기 때문에 탐색종료

 

Count = 2

 

결과로 2를 출력합니다.

 

이 문제에서 저는 소수를 확인하기 위해 에라토스테네스의 체를 사용하였습니다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

간단하게 설명하면 2 ~ N의 제곱근에서 소수인 값들의 자신을 제외한 배수는 소수가 아닙니다.

예를 들어

N = 35일 때

N의 제곱근 =  5.xxxxxx

2 ~ 35 중

2를 제외한 2의 배수는 소수가 아니다.

3을 제외한 3의 배수는 소수가 아니다.

5을 제외한 5의 배수는 소수가 아니다.

 

4는 소수가 아니기 때문에 배수를 통해 소수를 확인할 필요가 없습니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 2~N까지 배열과 에라토스테네스의 체를 이용하여 소수를 확인합니다.

2. 위 규칙을 적용하여 투 포인터 알고리즘을 수행합니다.

3. 조건에 만족한 경우의 범위의 경우의 수를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 에라토스테네스의 체를 이용하여 2~N 중 소수를 확인하였습니다.
• 규칙을 적용하여 범위의 소수의 합이 N이 되는 경우의 수를 구하는 cal함수를 만들었습니다.
• BufferedWriter에 경우의 수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal은 투 포인터 알고리즘을 통해 Start, End를 이용해서 경우의 수를 구하였습니다.
• cal은 반복문을 통해 위 규칙을 적용하였습니다.
• cal은 다음 소수를 확인하기 위해 반복문으로 진행하였습니다.

import java.io.*;
public class Main{
	static boolean[] notDecimal;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	int N = Integer.parseInt(br.readLine());
    	notDecimal = new boolean[N+1];
        //에라토스테네스의 체 구현 반복문
    	for(int i=2;i<=Math.sqrt(N);i++) {
    		if(!notDecimal[i]) {
        		for(int j=2;i*j<=N;j++)
        			notDecimal[i*j] = true;
    		}
    	}
    	int result = cal(N);		//함수 실행 및 결과 저장
    	bw.write(result + "\n");		//경우의 수 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //투 포인터 알고리즘을 이용하여 소수 합이 N이 되는 경우의 수 구하는 함수
    static int cal(int N) {
    	int start = 2;		//포인터 Start
    	int end = 2;		//포인터 End
    	int count = 0;		//경우의 수
    	int sum = 2;		//현재 범위 소수의 합
    	while(end<=N) {
    		if(sum < N) {	//규칙 1.
    			for(;;) {	//다음 소수를 찾기 위해 반복문 사용
    				end++;
        			if(end>N)
        				return count;
        			if(!notDecimal[end]) {
        				sum += end;		//범위 소수의 합 조정
        				break;
        			}
    			}
    		}else {		//규칙1, 규칙2
    			if(sum==N)		//규칙1 Count + 1 
    				count++;
    			
       			sum =  sum - start;		//범위 소수의 합 조정
    			for(;;) {		//다음 소수를 찾기 위해 반복문 사용
    				start++;
    				if(start>N)
    					return count;
    				if(!notDecimal[start])
    					break;
    			}
    		}
    	}
    	return count;		//경우의 수 반환
    }
}