글 읽기 - 예제는 다 맞는데...답이 자꾸 틀리네요. 잘 모르겠습니다ㅜ

kookmingosu 1년 전 0

예제는 다 맞는 걸 보니 아이디어는 괜찮은 것 같은데..

질문 게시판에 있는 반례들 넣어보면 다 틀리네요. 어떤 부분에서 그럴까요?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
bool a[4000001];

int main() {
	int cnt = 0;
	int n;
	cin >> n;
	fill_n(a, n + 1, 1);
	for (int i = 2; i <= sqrt(n); i++) { //소수판별
		if (a[i] == 0)
			continue;
		for (int j = 2 * i; j <= n; j += i)
			a[j] = 0;
	}
	vector<int> vec;
	for (int i = 2; i <= n; i++) //소수만 vec에 push
		if (a[i] == 1)
			vec.push_back(i);
	vector<int> sum;
	sum.push_back(0);
	if (n == 1) { 
		cout << 0 << '\n';
		return 0;
	}
	sum.push_back(vec[0]);
	for (int i = 1; i < vec.size(); i++) //소수 누적합 구하기
		sum.push_back(vec[i] + sum.back());
	for (int i = 0; i < sum.size(); i++) { //i기준으로 이분탐색
		int left = i + 1;
		int right = sum.size() - 1;
		while (left <= right) {
			int mid = (left + right) / 2;
			int ans = sum[mid] - sum[i];
			if (ans > n)
				right = mid - 1;
			else if (ans == n) {
				cnt++;
				break;
			}
			else
				left = mid + 1;
		}
	}
	cout << cnt << '\n';

	


	return 0;
}

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

문제

문제

출처

ICPC

예제는 다 맞는데...답이 자꾸 틀리네요. 잘 모르겠습니다ㅜ

kookmingosu 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말