글 읽기 - 안녕하세요 c++로 짠 문제 질문드립니다!

yeasung67 3년 전 0

안녕하세요 골드바흐 문제를 에라토스테네스 체를 이용해서 풀기 위해 이렇게 짰습니다

테스트케이스나 예외체크를 모두 해봤는데 답이 제대로 출력되어서 코드가 맞을 줄 알았습니다

그런데 제출했을 때 "시간초과"로 나오는 것도 아니고 "틀렸습니다"로 나오더라고요

결국 어찌저찌 검색하고 찾아본 결과

제가 짠 코드 중에 주석처리한 부분인 "//입력된 짝수가 두개의 홀수 소수의 합으로 표현되는지 확인"

하는 부분의 코드에서 틀린것 같더라고요

이유는 "굳이 모든 경우를 체크할 필요가 없고 답이 나오는 경우만 찾으면 된다" 인거 같더라고요

결국 범위 안에 소수집합과 개수를 저장해서 그 안에서 찾는 방식으로 했는데

사실 제가 짠 코드를 틀렸다고 봐야하는지 납득이 잘 안가서요 ㅜ

제가 짠 코드는 범위 안에 홀수인 수중에 소수를 찾아서 확인하는 방식인 건데

이게 차이가..? 있나요 아니면 제가 생각 못한 무언가 있을까요?

고수님들의 답변을 기다립니다!

*********************************************************

그리고 추가 질문으로 수정한 코드에서

처음에 main함수 안에 int prime[MAX]를 포함 시켰었는데

프로그램을 실행시키기도 전에 컴파일러가 스택을 초과하는 코드라고 경고를 주더군요

그래서 컴파일해서 확인해보니 바로 에러가 나더군요

근데 글로벌 베리어블로 만들면 오류가 안나는데 그 이유도 궁금합니다..!

메모리 영역에서 글로벌 베리어블을 저장하는 부분이 따로 있는 건 알고는 있는데

어떤 크기 정도가 스택영역을 벗어나게 되는지 궁금하네요

감사합니다 ㅠ

//처음에 제출 했을 때 틀렸던 코드
#include <iostream>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	//에라토스테네스의 체를 위한 반복문
	const int MAX = 1000000;
	bool check[MAX + 1] = { false, };

	check[0] = check[1] = true;

	for (int i = 2; i * i <= MAX; i++) {
		if (check[i] == false) {
			// n입력에서 짝수가 아닌 홀수가 입력되었을 경우 오류 출력을 위한 체크
			if (i == 2)
				check[i] = true;

			for (int j = i + i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}
	//문제풀이를 위한 반복문
	while (1) {
		int n;
		cin >> n;

		if (n == 0) // 0이 입력 되었을 때 종료
			break;
		//입력된 짝수가 두 개의 홀수 소수의 합으로 표현되는지 확인
		int i;
		for (i = 3; i <= n; i += 2) {
			if (check[n - i] == false) {
				cout << n << " = " << i << " + " << n - i << '\n';
				break;
			}
		}
		//만일 범위 안에서 못찾게 되면 메세지 출력
		if (i >= n) {
			cout << "Goldbach's conjecture is wrong\n";
		}
	}

	return 0;
}

/* 수정해서 맞은 코드
#include <iostream>
using namespace std;
const int MAX = 1000000;
bool check[MAX + 1] = { false, };
int prime[MAX];
int pn = 0;

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

	check[0] = check[1] = true;

	for (int i = 2; i * i <= MAX; i++) {
		if (check[i] == false) {
			prime[pn++] = i;

			for (int j = i + i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}

	while (1) {
		int n;
		cin >> n;
		
		if (n == 0)
			break;
            
        //이 부분에서 위에 코드와 차이가 있습니다
		int i;
		for (i = 1; i < pn; i++) {
			if (check[n - prime[i]] == false) {
				cout << n << " = " << prime[i] << " + " << n - prime[i] << '\n';
				break;
			}
		}

		if (i >= pn) {
			cout << "Goldbach's conjecture is wrong\n";
		}
	}

	return 0;
}
*/

dldyddlwl 3년 전 1

아래 2개의 if문을 잘 살펴봅시다. n-i에서 i가 반드시 소수라는 근거가 없습니다. 그에 반해서, n-prime[i] , prime[i] 소수라는 보장이 있습니다.

이것이 왜 문제가 되는 걸까요?

n - i = p ( 여기서 p는 소수 ) , n = p + i ( i는 소수가 아닐 수 있음에도 if문을 통과 )

Ex) n = 16이라고 합시다, 이 때, i 값이 9라면, 16-9 = 7 소수가 나옵니다, 그렇다면 if문을 통과하게 되어서,

16 = 9 + 7 이라는 잘못된 답이 나오게 됩니다.

2) 두 번째 질문, 어떤 환경에서 하셨는 지는 잘 모르겠지만, 얼마나 커야 스택 영역을 벗어나는 지는 다릅니다. 비쥬얼 스튜디오에서는 1MB로 두고 있습니다.

if (check[n - i] == false)
    
if (check[n - prime[i]] == false)

yeasung67 3년 전 0

감사합니다 위에꺼 이해가 됐습니다!

아래꺼는 서치해보니까 컴파일러로 스택의 크기를 조절할 수도 있더군요

답변해주셔서 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

안녕하세요 c++로 짠 문제 질문드립니다!

yeasung67 3년 전 0

dldyddlwl 3년 전 1

yeasung67 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말