[ 백준 BOJ / c++ ] 17103번 골드바흐 파티션

 

🤔 문제

 

링크 : https://www.acmicpc.net/problem/17103

 

---

👀 접근 방식

"에라토스테네스의 체 " 알고리즘으로 모든 소수를 구한뒤, "투 포인트" 알고리즘으로 모든 소수를 좌우로 조금씩 좁혀 찾아 같은지 검사하였다.

 

1. 에라스토 테네스의 체 알고리즘으로 모든 소수를 벡터에 저장
2. t번의 입력을 받음
   1. 입력값이 벡터에 존재 -> 개수 1로 설정
   2. 투포인트 알고리즘으로 2와 소수 최대값 부터 조금씩 값을 줄여 개수를 구함
   3. 개수 출력

---

💻 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int sosus[1000001];
vector<int> arr;

void process()
{
	int num; cin >> num;

	int cnt = 0;

	// 현재 num이 소수일시 cnt값을 1로 시작
	if (!sosus[num])
		cnt = 1;

	// tow point 알고리즘
	int leftIndex = 0;
	int rightIndex = arr.size()-1;

	while (leftIndex <= rightIndex)
	{
		
		int rightValue = arr[rightIndex];
		int leftValue = arr[leftIndex];
		int targetValue = rightValue + leftValue;

		if (targetValue > num)
		{
			rightIndex--;
		}
		else if (targetValue < num)
		{
			leftIndex++;
		}
		else {
			cnt++;
			leftIndex++;
		}

	}

	cout << cnt << endl;

}

int main()
{
	/*
		1. 에라스토 테네스의 체 알고리즘으로 모든 소수를 벡터에 저장
		2. t번의 입력을 받음
			2-1 . 입력값이 벡터에 존재 -> 개수 1로 설정
			2-2 . 투포인트 알고리즘으로 2와 소수 최대값 부터 조금씩 값을 줄여 개수를 구함
			2-3 . 개수 출력
	*/

	//에라토스테네스의 체
	for (int i = 2; i < 1000001; ++i)
	{
		for (int j = 2; i*j < 1000001; ++j)
		{
			sosus[i * j] = 1;
		}
		if (sosus[i] == 0)
			arr.push_back(i);
	}

	// t만큼 실행
	int t; cin >> t;

	while (t--)
	{
		process();
	}

	return 0;
}