글 읽기 - 아 이게 진짜 왜 틀린지 이해가 안됩니다.

speedheawon 2년 전 0

단순히 생각했을 때 B 배열을 움직여도 결과에 영향을 미치지 않는 것 같아서

A배열을 큰 수부터 정렬하고 B배열을 작은 수부터 정렬해서,

A[i] * B[i] 값들을 더했는데, 왜 정답이 나오지 않는 건가요?

입력 형식의 문제인지, 제가 조건을 잘못 본 건지 1시간을 붙잡아도 모르겠어서 질문 글 올립니다.

다들 쉽게 푸는 것 같은데, 막혀서 정답을 못 찾으니 당황스럽네요.

정답 S 값의 범위는 최대 500000이니 오버 플로우가 발생하는 것도 아닌 것 같습니다.

#include <iostream>
#include <algorithm>
using namespace std;

void input();
void greedy();
void printAns();
bool comp(int a, int b);

int arrA[51];
int arrB[51];
int n;
int sum = 0;

int main(void)
{
	input();
	greedy();
	printAns();

	return 0;
}
void input()
{
	scanf("%d", &n);

	for(int i = 0; i < n; i++)
		scanf("%d", &arrA[i]);

	for(int i = 0; i < n; i++)
		scanf("%d", &arrB[i]);
}
void greedy()
{
	sort(arrA, arrA + n, comp);
	sort(arrB, arrB + n);

	for(int i = 0; i < n; i++)
		sum += arrA[i] * arrB[i];
}
bool comp(int a, int b)
{
	if(a >= b)
		return true;
	else
		return false;
}
void printAns()
{
	printf("%d\n", sum);
}

speedheawon 2년 전 0

진짜 생각도 못한 오류였네요.

이론상으로는 문제 없었는데 구현상으로 문제가 있었습니다.

comp 함수에서

if(a >= b) 라고 정의해 놓으니 입력을 아래와 같이 주면

50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2

i: 0 A: 1 B: 1 S: 1
i: 1 A: 1 B: 1 S: 1
i: 2 A: 1 B: 1 S: 1
i: 3 A: 1 B: 1 S: 1
i: 4 A: 1 B: 1 S: 1
i: 5 A: 1 B: 1 S: 1
i: 6 A: 1 B: 1 S: 1
i: 7 A: 1 B: 1 S: 1
i: 8 A: 1 B: 1 S: 1
i: 9 A: 1 B: 1 S: 1
i: 10 A: 1 B: 1 S: 1
i: 11 A: 1 B: 1 S: 1
i: 12 A: 1 B: 1 S: 1
i: 13 A: 1 B: 1 S: 1
i: 14 A: 1 B: 1 S: 1
i: 15 A: 1 B: 1 S: 1
i: 16 A: 1 B: 1 S: 1
i: 17 A: 1 B: 1 S: 1
i: 18 A: 1 B: 1 S: 1
i: 19 A: 1 B: 1 S: 1
i: 20 A: 0 B: 1 S: 0
i: 21 A: 0 B: 1 S: 0
i: 22 A: 0 B: 1 S: 0
i: 23 A: 0 B: 1 S: 0
i: 24 A: 0 B: 1 S: 0
i: 25 A: 0 B: 1 S: 0
i: 26 A: 0 B: 1 S: 0
i: 27 A: 0 B: 1 S: 0
i: 28 A: 0 B: 1 S: 0
i: 29 A: 0 B: 1 S: 0
i: 30 A: 0 B: 1 S: 0
i: 31 A: 0 B: 1 S: 0
i: 32 A: 0 B: 1 S: 0
i: 33 A: 0 B: 1 S: 0
i: 34 A: 1 B: 1 S: 1
i: 35 A: 1 B: 1 S: 1
i: 36 A: 1 B: 1 S: 1
i: 37 A: 1 B: 1 S: 1
i: 38 A: 1 B: 1 S: 1
i: 39 A: 1 B: 1 S: 1
i: 40 A: 1 B: 1 S: 1
i: 41 A: 1 B: 1 S: 1
i: 42 A: 1 B: 1 S: 1
i: 43 A: 1 B: 1 S: 1
i: 44 A: 1 B: 1 S: 1
i: 45 A: 1 B: 1 S: 1
i: 46 A: 1 B: 1 S: 1
i: 47 A: 1 B: 1 S: 1
i: 48 A: 1 B: 1 S: 1
i: 49 A: 1 B: 2 S: 2

중간에 데이터 몇개가 날라갑니다.

이유는 저도 잘 모르겠네요.

조건을 만족하면 두 배열의 위치를 바꾸고, 만족하지 않으면 바꾸지 않는게

sort의 알고리즘 아니였나요?

아무튼

if(a > b) 로 바꾸니 문제가 해결되었습니다.

qvixnh22 2년 전 1

c++ algorithm 헤더의 sort 함수의 비교는 비교할 때 두 수가 같은 경우 false를 반환해야 합니다.

speedheawon 2년 전 0

그렇습니다. 이 글을 올리고 난 뒤 알게 된 사실인데,

비교에 이용되는 함수는 두 수가 같은 경우 false를 반환해야 하는비반사성을 만족시켜야 한답니다.

새롭게 하나 배워가는군요...

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

문제

문제

출처

ICPC

아 이게 진짜 왜 틀린지 이해가 안됩니다.

speedheawon 2년 전 0

speedheawon 2년 전 0

qvixnh22 2년 전 1

speedheawon 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말