[백준] 1644.소수의 연속합 (java) / 투포인터, 슬라이딩 윈도우, 에라토스테네스의 체(소수 구하기)

@투포인터, 슬라이딩 윈도우, 에라토스테네스의 체(소수 구하기) / 1h 25m

문제를 읽어보고 슬라이딩 윈도우라는 것은 알았는데,

소수 구하는 방법을 따로 몰라서 직접 구현했더니 시간 초과..ㅎㅎ

그래서 에라토스테네스의 체 라는 방법을 공부해서 풀었다.

 

 

문제 링크

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

 

구현 포인트

이 문제를 풀기 위해서는

1. 소수 구하기 알고리즘(에라토스테네스의 체)

2. 슬라이딩 윈도우

개념이 필수적이라고 생각한다.

 

1번의 경우 의외로 위키백과에 설명이 잘 되어 있고, 그림도 이해하기 쉽게 되어 있어서 이걸로 공부했다. 설명만 잘 읽어보면 밑의 코드를 안 보고도 짤수 있을 것이다.

 

아, 설명에서 하나 헷갈리던 부분은 이 부분이었는데,

생각해 보면 11과 소수를 곱한 수는 11 * 3, 11 * 5, 11 * 7, 11 * 11....이다

여기서 밑줄 친 세 수는 이미 11의 배수까지 가기 전에 3의 배수, 5의 배수, 7의 배수에서 다 지워진다.

그럼 11 * 11부터 남는데, 이 값은 어차피 주어진 값을 초과하기 때문에 신경 쓸 필요가 없다.

 

그래서, 코드 상에서 배수들을 지워줄 때

int end = Math.sqrt(N); 이렇게만 해주고, + 1을 따로 해주지 않아도 괜찮다.

만약 N이 120이면 end는 10이 될텐데, 10까지의 배수들만 지워주면 되기 때문이다.

 

2번의 경우, 이 블로그의 설명이 굉장히 잘 되어 있어서, 이걸로 공부했다.

 

 

삽질 포인트

1. 처음 문제를 풀었을 때는 시간초과가 났는데, 소수 구하는 부분을 내 코드->에라토스테네스의 체 코드로 변경하니 통과됐다.

 

2. 문제를 잘못 이해해서, 소수들의 합 또한 소수여야 한다고 생각했다. 그래서 틀렸었다. 문제 똑바로 읽어야 할 듯..

 

 

코드

+ 이 코드는 소수가 아닌 수들을 true로 바꾸게 코드를 짰다.

+ 처음 공부한 개념들이라 헷갈리는게 많아서, 주석을 자세하게 써놨다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static int N, rslt = 0, arr[], arrSize;
	static boolean[] check;
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		N = s.nextInt();
		
		arr = new int[N + 1];
		check = new boolean[N + 1];
//		if (check[N]) rslt++;		
		//만약 자기자신도 소수라면 rslt를 하나 추가해준다 로 하려했는데
		//어차피 이것까지 슬라이딩 윈도우가 다 해

		checkNum();
		makeArr();
		slide();
		
		System.out.println(rslt);
	}

	private static void slide() {
		int s, e, sum;
		s = e = sum = 0;
		
		while (true) {
			if (sum >= N) sum -= arr[s++];
			//끝 인덱스는 포함하지 않으므로, arrSize - 1로 하면 안된다 
			else if (e == arrSize) break;
			else sum += arr[e++];
			if (sum == N) rslt++;
		}
	}

	private static void checkNum() {
		//만약 N = 120이면 end = 10인데, +1은 굳이 안해줘도 된다 
		//왜냐하면 11 * 11 > 120이므로. 11* 2, 3, 4,... 이런건 이미 이전에 지워졌기 때문에 상관 없다 
		int end = (int)Math.sqrt(N);
		
		int num = 2;
		while (num <= end) {
			//자기 자신은 지우면 안된다!
			for (int i = num * 2; i <= N; i += num)
				//소수가 아닌 수들을 true로 바꿔준다 
				check[i] = true;

			num = searchNum(num);
		}
	}

	private static int searchNum(int num) {
		while (num < N)
			// 그 다음으로 지워줄 소수를 찾는다 
			if (!check[++num])
				return num;
		
		//지워줄 소수가 없다면, 이렇게 넘겨주면 while의 조건에 걸려서 자동으로 종료된다 
		return num + 1;
	}
	
	private static void makeArr() {
		int idx = 0;
		for (int i = 2; i <= N; i++)
			if (!check[i])
				arr[idx++] = i;
		arrSize = idx;	//size니까 1 큰 상태로 저장 
	}
}

처음 써보는 개념들이라 살짝 헷갈리긴 했는데

재밌는 문제였다.

 

끝!