글 읽기 - [1024 수열의 합] 반례를 못 찾겠습니다. 도움 주시면 감사하겠습니다.

park345601 3년 전 0

나름 주석도 이쁘게 달았습니다..

1024 수열의 합 문제입니다.

질문 게시판에 있는 모든 반례도 테스트해보고 여러 값을 넣어보면서 디버깅해봤는데 왜 틀린지 모르겠습니다.

처음에 배열의 크기 100을 체크 안해줬길래 그건줄 알았는데 고쳤는데도 같은 곳에서 틀리더라구요..

꼭 좀 반례 찾아주시면 감사하겠습니다..!

#include <iostream>
#include <vector>

void Solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	Solve();
}

bool isNotAnswer(const int n, const int l, std::vector<int>& answer)
{
	int p = n / l;
	int right = p + (l / 2); // 수열의 최대값
	int left = p - ((l - 1) / 2); // 수열의 최소값

	if (left < 0) // 수열 음수 방지
		return true;

	// 수열의 합 계산 (1부터 right(수열의 최대)까지의 합 - 1부터 left(수열의 최소)까지의 합)
	int64_t sum = int64_t(right * (right + 1) / 2) - int64_t(left * (left - 1) / 2);
	
	if (n != sum)
		return true;

	// 수열의 합이 n인 경우 수열을 만듬
	for (int i = left; i <= right; i++)
		answer.push_back(i);

	return false;
}

void Solve(void)
{
	int n, l;
	std::cin >> n >> l;

	std::vector<int> answer;
	while (l <= 100 && isNotAnswer(n, l, answer))
		l++;

	if (answer.empty() || 100 < answer.size())
	{
		std::cout << -1;
		return;
	}

	for (auto a : answer)
		std::cout << a << " ";
}

tor012 3년 전 1

첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.

라는 조건에 따라

18번 right의 최대값은 n이 10억, l이 2억일때, 5억*5억 정도의 값을 가질 수 있게 되고 이는 int 범위를 넘어서므로 오버플로우로 인해 제대로 된 결과를 기대하기 어렵습니다.

5억*5억을 다룰 수 있는 자료형을 사용하셔서 시도해보십시오.

tor012 3년 전 1

n이 10억, l이 2억

에서 l이 2 일떄 입니다. 2억은 오타입니다..

park345601 3년 전 0

아 right의 범위가 문제일 줄은 몰랐네요!!

sum을 계산하는 도중에 오버플로우가 발생하는거였군요..!

정말 감사합니다 :D

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

문제

문제

출처

ICPC

[1024 수열의 합] 반례를 못 찾겠습니다. 도움 주시면 감사하겠습니다.

park345601 3년 전 0

tor012 3년 전 1

tor012 3년 전 1

park345601 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말