백준 1644 - 소수의 연속합(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

에라토스테네스의 체 + 두 포인터가 합쳐진 문제였습니다.

문제 조건

출력 예시

1 ~ N까지의 수에서 소수를 판정한 뒤, 해당 소수의 값들로 N을 만들 수 있는지 확인하면 되는 문제였습니다.

N의 범위가 최대 4,000,000 이여서 N*N크기의 2중 for문을 돌린다면 시간 초과가 생길 수 있습니다.

따라서 에라토스테네스의 체를 사용해주시면 됩니다. 

 

소수 판정이 끝났다면 소수가 있을 때와 소수가 없을 때로 나누어서 계산해야합니다.(소수가 없을 때를 고려하지 않아 계속 런타임 에러가 생겼습니다..)

소수가 없을 때에는 "0"을 바로 return 해주시면 됩니다.

소수가 있을 때는 아래 그림과 같이 작동하게 만들어줍니다.

해당 과정을 조건까지 반복해줍니다.

 

문제 접근 방법

1. 1 ~ N까지 소수를 구합니다.

2. low = high = 0부터 시작해 low ~ high까지 vector 값의 합에 따라서 high 또는 low값을 증가합니다.

 

 

문제 접근 방법 - 1번

void find_number() {
	check[1] = 1;
	for (int i = 2; i <= sqrt(N); i++) {
		if (check[i] == 0) {
			for (int j = i * 2; j <= N; j += i) {
				check[j] = 1;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		if (check[i] == 0) {
			prime_number.push_back(i);
		}
	}
}

에라토스테네스의 체 코드입니다.

 

문제 접근 방법 - 2번

void solve() {
	find_number();
	if (prime_number.size() == 0) cout << "0";
	else {
		int low = 0;
		int high = 0;
		int ans = 0;
		int sum = prime_number[0];
		while (high < prime_number.size() && low <= high) {
			if (prime_number[low] > N) break;
			if (sum < N) {
				if (high < prime_number.size() - 1) {
					high++;
					sum += prime_number[high];
				}
				else break;
			}
			else if (sum >= N) {
				if (sum == N) ans++;
				sum -= prime_number[low];
				low++;
			}
		}
		cout << ans;
	}
}

소수가 없을 경우 -> 0을 출력

소수가 있을 경우 -> 탐색 시작

1. low ~ high까지의 값이 N보다 작을 경우 -> high를 증가합니다

2. low ~ high까지의 값이 N과 같은 경우 -> ans와 low를 증가합니다.

3. low ~ high까지의 값이 N보다 큰 경우 -> low를 증가합니다.

 

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N;
vector<int> prime_number;
int check[4000001];

void find_number() {
	check[1] = 1;
	for (int i = 2; i <= sqrt(N); i++) {
		if (check[i] == 0) {
			for (int j = i * 2; j <= N; j += i) {
				check[j] = 1;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		if (check[i] == 0) {
			prime_number.push_back(i);
		}
	}
}

void solve() {
	find_number();
	if (prime_number.size() == 0) cout << "0";
	else {
		int low = 0;
		int high = 0;
		int ans = 0;
		int sum = prime_number[0];
		while (high < prime_number.size() && low <= high) {
			if (prime_number[low] > N) break;
			if (sum < N) {
				if (high < prime_number.size() - 1) {
					high++;
					sum += prime_number[high];
				}
				else break;
			}
			else if (sum >= N) {
				if (sum == N) ans++;
				sum -= prime_number[low];
				low++;
			}
		}
		cout << ans;
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!