c언어 9873번 Cow Baseball (백준)

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) { //qsort 을 위한 함수
	return *(int*)a - *(int*)b; //오름차순 정렬
}

int main(void) {
	int n,n1,n2,gap1,gap2,ans=0;
	scanf("%d",&n); //입력
	n1=n-1;n2=n-2;
	int *a = (int *) malloc(sizeof(int)*n); //동적 할당
	for(int i=0; i<n; i++) scanf("%d",&a[i]); //입력
	qsort(a,n,sizeof(int),compare); //정렬
    
	for(int i=0; i<n2; i++) { //브루트 포스
		for(int j=i+1; j<n1; j++) {
			gap1 = a[j]-a[i];
			for(int k=j+1; k<n; k++) {
				gap2 = a[k]-a[j];
				if(gap1 > gap2);
				else if(gap1*2 < gap2) break; //처음보다 2배 초과라면 더 이상 반복할 필요가 없다
				else ++ans;
			}
		}
	} printf("%d",ans);
    free(a);
}

 

풀이 : 정렬, 브루트 포스

 

오름차순으로 정렬을 한 다음

브루트 포스로 X Y Z에서 Y와 X차이와 같거나 Y와 X차이의 2배 이하인 Z와 Y의 차이인  X Y Z의 쌍을 구했습니다.

 

이분탐색이나 다른 방식을 사용하거나, 정렬을 더욱 빠른 걸로 하면 소요시간을 줄일 수 있다고 생각합니다.

 

https://www.acmicpc.net/problem/9873