글 읽기 - 안녕하세요. 반례찾는 과정에서 질문이 있습니다.

spearkkk 7년 전 0

안녕하세요.

우선 문제에 대해서 이해한 바는 정수 N개가 들어 왔을 때,

모두 다른 정수로 판단하여 순서쌍을 만들고 서로 곱한 값의 합을 구하는 문제입니다.

예를 들어 N = 4로, 2, 2, 3, 4가 있을 때, (2, 2), (2, 3), (2, 4), (2, 3), (2, 4), (3, 4) 총 6개의 케이스가 나옵니다.

이 부분에 대해서 잘못 이해한 것이라면 알려주세요.

제가 이해한 문제를 풀기위해 알고리즘은 다음과 같습니다.

1. 한 정수를 빼고 나머지 숫자들의 합과 곱한다.

2. 모든 정수가 나올 때까지 반복한다.

3. 이 과정에서 나온 곱한 값들의 합을 출력한다.

입력 예제의 답은 다 맞습니다. 반례가 떠오르지가 않습니다.

제가 진행한 알고리즘에 문제가 있을까요?

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int MAX = 100000;
int n;
int arr[MAX];
int total = 0;
unsigned long long rslt = 0;

int main() {
	memset(arr, 0, sizeof(arr));

	//for (int i = 0; i < MAX; ++i) {
	//	arr[i] = 10000;
	//	total += arr[i];
	//}

	//printf("%llu\n", total);

	scanf("%d", &n);
	fgetc(stdin);
	
	for (int i = 0; i < n; ++i) {
		scanf("%d", &arr[i]);
		fgetc(stdin);
		total += arr[i];		
	}

	for (int i = 0; i < n - 1; ++i) {
		total -= arr[i];
		rslt += total * arr[i];	
	}

	printf("%llu\n", rslt);
	//printf("%llu\n", ULLONG_MAX);

	return 0;
}

doju 7년 전 1

rslt += total * arr[i]; 부분에서 total 과 arr[i] 가 둘 다 int 형이므로 곱할 때 integer overflow가 일어날 수 있습니다.

spearkkk 7년 전 0

감사합니다.

덕분에 해결했습니다.

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

문제

문제

출처

ICPC

안녕하세요. 반례찾는 과정에서 질문이 있습니다.

spearkkk 7년 전 0

doju 7년 전 1

spearkkk 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말