[BOJ] 1644 소수의 연속합 (C/C++)

1644번: 소수의 연속합

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 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학년 때에 한번쯤은 했을 것 같은데 기억이 전혀 안 난다.

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

위키에 있는 애니메이션을 보고나서 에라토스테네스씨 이름이 지금까지 내려오는 데에는 다 이유가 있다고 생각했다. 히트다 히트. 아무튼 이 문제는 에라토스테네스의 체를 이용해서 N까지의 소수를 미리 구한다. 최대 소수 개수는 구할 수 있지만 배열 사이즈 잡기 귀찮아서 그냥 vector를 사용했다.

 

소수의 개수를 미리 다 구한 이후에 포인터를 모두 0번 인덱스에서 시작한다. 부분합을 구해가면서 조건에 따라서 포인터를 이동한다. 이때 while에 right < size라고 조건을 넣었다가 계속 답이 안 나왔는데 그 이유가 right가 N에 도달한 이후에도 left를 올리면서 부분합을 확인해야 되는데 while문을 그냥 튀어나가 버렸다. 그 조건을 while문 안에서 처리하니까 답이 나왔다.

 

	#include <iostream>
	#include <vector>
	using namespace std;
	int N;
	vector<int> prime;
	vector<bool> check;
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	check.resize(N + 1, true);
	for (int i = 2; i * i <= N; i++){
	if (!check[i]) continue;
	for (int j = i * i; j <= N; j += i){
	check[j] = false;
	}
	}
	for (int i = 2; i <= N; i++) {
	if (check[i]) prime.push_back(i);
	}
	int ans = 0; int sum = 0;
	int left = 0; int right = 0;
	int size = prime.size();
	while (1) {
	if (sum >= N) {
	sum -= prime[left++];
	}
	else if (right == size) break;
	else {
	sum += prime[right++];
	}
	if (sum == N) {
	ans++;
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw 1644.cpp hosted with ❤ by GitHub

후기)

투 포인터라고 이름이 붙어서 뭔가 하나의 방법이 있다기보단 포인터 두개 쓰면 투 포인터구나...