글 읽기 - 똑같은 코드를 배열대신 벡터를 사용했을때 틀렸습니다 뜨는데 이유가뭘까요?

malratz 4년 전 0

안녕하세요

https://www.acmicpc.net/board/view/35391

이 질문이랑 똑같은 알고리즘으로 풀었는데, 배열 대신 벡터를 사용헀습니다.

테스트 값은

999100 - 1000000 을 줬습니다.

근데 결과값이 다른 이유가 뭘까요?

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	bool check[1000001];
	vector<int> v;
	
	for(int i=2; i<=1000000; i++) {
		if(check[i] == false) {
			for(int j=i+i; j<=1000000; j+=i) check[j]=true;
		}
	}
	
	int cnt=0;
	for(int i=2; i<=500000; i++) {
		if(check[i] == false) v.push_back(i);
	}
	
	int T;
	cin>>T;
	for(int i=0; i<T; i++) {
		int num;
		cin>>num;

		int total=0;
		for(int j=0; j<v.size() && v[j] <= num/2; j++) {
			if(check[num-v[j]]==false) total++;
		}
	
		cout<<total<<'\n';
	}
	
	return 0;
}

skysign 3년 전 0

1. 문제의 일부분을 발췌해 보면, '두 소수의 순서만 다른 것은 같은 파티션이다.' 라고 되어 있어요,

위의 제가 코드를 디버깅해 보지는 않았지만, 코드 리뷰해본 거로만 말씀드릴께요.

같은 파티션이기 때문에, total 이 증가 하면 안되는 부분에서,

위의 코드에서 다른 파티션으로 total을 증가 시켰을 케이스가 있었을 것 같습니다.

위와 같은 문제를 막기 위해서,

num <= v[j] - num

이렇게 한번더 확인해야 합니다.

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

문제

문제

출처

ICPC

똑같은 코드를 배열대신 벡터를 사용했을때 틀렸습니다 뜨는데 이유가뭘까요?

malratz 4년 전 0

skysign 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말