PS/BOJ

1644

easy16 2022. 5. 4. 01:03

소수의 연속합 : https://www.acmicpc.net/problem/1644

 

숏코드 : https://www.acmicpc.net/source/22465860

 

 

에라토스테네스의 체가 생각보다 자주 쓰인다.

이번 숏코드에서는 해당 코드를 변형하여 문제에 활용한 것이 눈에 띈다.

 

기존에는 0,1로 소수 여부를 판단했으나,

숏코드에서는 소수는 자기 자신, 나머지는 0으로 초기화 하면 이후 계산에 있어 이득을 볼 수 있다.

 

//개선

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N, S, answer = Integer.MAX_VALUE;
	static int[] arr;
	private static boolean DBG = false;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		arr = new int[N + 1];

		// init
		eratostenesSphare();

		int lt = 0, rt = 0;
		int sum = 0, cnt = 0;

		while (rt <= N) {

			while (sum < N && rt <= N) {
				sum += arr[rt++];				
				if (DBG)
					System.out.printf("R[%d %d] sum :%d \n", lt, rt, sum);
			}
			while (sum > N && lt < rt) {
				sum -= arr[lt++];
				if (DBG)
					System.out.printf("L[%d %d] sum :%d\n", lt, rt, sum);
			}

			if (sum == N) {
				cnt++;
				while(arr[lt]==0 && lt< rt) lt++;
				sum -= arr[lt++];				
				if (DBG)
					System.out.printf("=[%d %d] sum :%d cnt : %d\n", lt, rt, sum, cnt);
			}

		}

		System.out.println(cnt);
	}

	static void eratostenesSphare() {
		
		for ( int i = 2 ; i <= N ;i++)
			arr[i] = i;
		
		for (int i = 2; i <= N; i++) {						
			for (int j = i * 2; j <= N; j += i) {
				arr[j] = 0;
			}
		}
	}

}

 

//기존 제출

//최초 AC
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N, S, answer = Integer.MAX_VALUE;
	static int[] arr;
	private static boolean DBG = false;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		arr = new int[N + 1];

		// init
		eratostenesSphare();

		int lt = 0, rt = 0;
		int sum = 0, cnt = 0;

		while (rt <= N) {

			while (sum < N && rt <= N) {
				sum += (arr[rt] == 0 ? rt : 0);
				rt++;
				if (DBG)
					System.out.printf("R[%d %d] sum :%d \n", lt, rt, sum);
			}
			while (sum > N && lt < rt) {

				sum -= (arr[lt] == 0) ? lt : 0;
				lt++;
				if (DBG)
					System.out.printf("L[%d %d] sum :%d\n", lt, rt, sum);
			}

			if (sum == N) {
				cnt++;
				while (arr[lt] == 1 && lt < rt) {
					lt++;
				}
				sum -= (arr[lt] == 0) ? lt : 0;
				lt++;
				if (DBG)
					System.out.printf("=[%d %d] sum :%d cnt : %d\n", lt, rt, sum, cnt);
			}

		}

		System.out.println(cnt);
	}

	static void eratostenesSphare() {
		arr[0] = arr[1] = 1;
		for (int i = 2; i <= N; i++)
			for (int j = i * 2; j <= N; j += i)
				arr[j] = 1;
	}

}