홍장알 바로가기

문제

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

⭕ 맞았습니다!!

에라토스테네스의 체를 사용하여 소수를 모두 구해두었다.
그 다음, 주어진 숫자를 홀수 소수의 합으로 구할 수 있는지 살펴보았다.
불가능한 경우를 나타내기 위해 투포인터의 개념을 적용하였다.

#include <iostream>
#include <math.h>
using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int primeNum[1000001] = { 0, };

	primeNum[1] = 1;
	for (int i = 2; i <= sqrt(1000000); i++) {
		if (primeNum[i] == 1) continue;
		for (int j = 2 * i; j <= 1000000; j += i) {
			primeNum[j] = 1;
		}
	}

	int n;
	while (1) {
		cin >> n;
		if (n == 0) break;
		
		for (int left = 3; left <= n / 2 + 1; left += 2) {
			int right = n - left;
			if (left > right) {
				cout << "Goldbach's conjecture is wrong.\n";
				break;
			}
			if (primeNum[left]) continue;
			if (primeNum[right] == 0) {
				cout << n << " = " << left << " + " << right << '\n';
				break;
			}
		}
	}
	return 0;
}

Stack Overflow

문제를 풀며 stack overflow를 마주하였다. 범위가 큰 primeNum 배열을 main 함수 내부에서 정의하여 발생한 것이였다.

그 원인은 배열이 할당되는 위치에 있었다.
main 함수 내에서 선언된 배열은 스택 영역에 생성된다. 스택영역은 프로그램이 사용하는 임시 메모리로 할량할 수 있는 정도가 적다.

해당 배열을 전역 변수로 설정하여 문제를 해결할 수 있었다.
전역변수로 변수를 선언하면 이는 함수가 호출되기 전에 메모리의 데이터 영역에 할당된다.

자세한 내용은 백준 게시판 질문, 위키백과의 참고2에서 살펴볼 수 있다.