글 읽기 - 1090번 문제 질문입니다..

lis301 4년 전 0

안녕하세요. 제가 생각한 알고리즘은 x y 좌표 각각의 평균값을 구한다음에, 평균값과 입력값 x y 좌표와의 차의 합을 r배열에 저장 한 후, 배열 r을 오름차순으로 정렬하여 출력하는 것입니다. 제가 생각한 케이스들은 모두 문제 없이 돌아갔습니다.. 코드상의 문제점이나 반례가 있나요?? 도와주세요 ㅠㅠㅠㅠ

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(){
	int n,tmp, result = 0;
	double avgx = 0, avgy = 0;
	scanf("%d", &n);
	int *x = (int*)malloc(sizeof(int)*n);
	int *y = (int*)malloc(sizeof(int)*n);
	int *r = (int*)malloc(sizeof(int)*n);
	for (int i = 0; i < n; i++){
		scanf("%d %d", &x[i], &y[i]);
		avgx += x[i]; avgy += y[i];
	}
	avgx = floor(avgx / n + 0.5);
	avgy = floor(avgy / n + 0.5);
	for (int i = 0; i < n; i++)
		r[i] = fabs(avgx - x[i]) + fabs(avgy - y[i]);
	for (int i = 0; i < n - 1; i++){
		for (int j = 0; j < n - 1; j++){
			if (r[j] > r[j + 1]){
				tmp = r[j];
				r[j] = r[j + 1];
				r[j + 1] = tmp;
			}
		}
	}
	printf("%d ", result);
	for (int i = 0; i < n; i++){
		result += r[i];
		if (i!=0) printf("%d ", result);
	}
	return 0;
}

lis301 4년 전 0

죄송한데 제가 생각한 방식으로 손으로 풀어보니 답이 제 프로그램 결과값과 똑같이 나옵니다.. 제 알고리즘 자체가 문제가 있는 걸까요?

0 299999 449999 600000

lis301 4년 전 0

제가 문제 이해를 못했었네요 ㅠ 정말 감사합니다!

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

문제

문제

출처

ICPC

1090번 문제 질문입니다..

lis301 4년 전 0

lis301 4년 전 0

lis301 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말