백준 9020 c++ "골드바흐의 추측" -PlusUltraCode-

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

 

[필자 사고]

에스테라토스의 채를 이용하여 푸는 소수문제이다.

사전에 먼저 소수들을 모두 찾았다.

그다음 소수를 저장할 배열에 모든 소수를 옮긴 뒤 브루트포스 알고리즘을 적용하여 모두 더했다.

문제에서 주어진 10000을 넘어가면 무시했따.

 

 그다음 우선순위큐를 이용하여 두 수를 더한 값이 차가 가장 작은 것을 먼저 우선순위로 정해서 문제를 해결했따.

 

지금 생각해보면 우선순위큐를 10000개를 생성하여 문제를 해결했는데 메모리 사용을 더 적게해서 문제를 풀 수 있었을거 같다.

[코드 해설]

🔹 전역 변수

• pq[10001]: 인덱스 n에 대해, 두 소수의 합이 n이 되는 모든 소수 쌍을 우선순위 큐에 저장합니다. 가장 차이가 적은 쌍이 우선적으로 나옵니다.
• numbers: 0부터 10000까지의 숫자 중 소수 여부를 저장하는 불리언 배열.
• sosuNumbers: 에라토스테네스의 체로 구한 소수 목록을 저장하는 벡터.

---

🔹 Input_Init() 함수

1. 에라토스테네스의 체를 이용해 소수를 판별하여 numbers 벡터에 저장합니다.
2. 소수 목록을 sosuNumbers에 저장합니다.
3. sosuNumbers를 2중 for문으로 순회하며, 두 소수의 합을 미리 계산합니다.
   • 합이 10000 이하일 경우, 그 합을 인덱스로 하는 pq[sum]에 (a, b) 쌍을 저장합니다.
   • priority_queue는 커스텀 정렬 기준 cmp를 통해 두 수의 차이가 가장 작은 쌍이 top에 오도록 합니다.

---

🔹 cmp 구조체

• 우선순위 큐의 정렬 기준을 정의합니다.
• abs(a - b)가 작을수록 우선순위가 높도록 만들어, 소수 쌍 중 가장 차이가 작은 조합을 먼저 출력하게 합니다.

---

🔹 Game_Start(int num) 함수

• 주어진 num에 대해, pq[num]의 top 값을 꺼내 출력합니다.
• 즉, num을 두 소수의 합으로 표현한 조합 중에서 차이가 가장 적은 소수 쌍을 출력합니다.

---

🔹 main() 함수

1. 테스트 케이스 수 T를 입력받습니다.
2. Input_Init()으로 미리 모든 수에 대한 소수 쌍을 계산하고 저장합니다.
3. 각 테스트 케이스마다 num을 입력받아 Game_Start(num)을 호출합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int N;
vector<vector<int>> arr;

void Input() {
	cin >> N;
	arr.assign(N + 1, vector<int>(N + 1));

	for (int i = 1; i <= N; i++) {
		string str;
		cin >> str;
		for (int k = 0; k < N; k++) {
			arr[i][k + 1] = str[k] - '0';
		}
	}
}

void DFS(int left, int right, int size) {

	if (size == 0) {
		cout << arr[left][right];
		return;
	}
	
	bool onlyOne = true;
	bool onlyZero = true;

	int nowNumber = arr[left][right];
	if (nowNumber == 1) {
		for (int i = left; i < left + size; i++) {
			for (int k = right; k < right + size; k++) {
				if (nowNumber != arr[i][k]) {
					onlyOne = false;
				}
			}
		}

		if (onlyOne == true) {
			cout << 1;
			return;
		}
	}
	else {
		for (int i = left; i < left + size; i++) {
			for (int k = right; k < right + size; k++) {
				if (nowNumber != arr[i][k]) {
					onlyZero = false;
				}
			}
		}
		if (onlyZero == true) {
			cout << 0;
			return;
		}
	}



	cout << '(';
	DFS(left, right, size / 2);                        // 좌상
	DFS(left, right + size / 2, size / 2);             // 우상
	DFS(left + size / 2, right, size / 2);             // 좌하
	DFS(left + size / 2, right + size / 2, size / 2);  // 우하
	cout << ')';
}

void Game_Start() {
	DFS(1, 1, N);
}

int main(void) {
	Input();
	Game_Start();
}