글 읽기 - 초보의 잡다한 질문입니다....

201023777 8년 전 0

10816번을 풀다가 int 형 배열이 2천만개나 잡히겠어? 하고는

정렬한 후에 최소값에서부터 출발해서 값을 더해나가는 과정을 구현해봤습니다만... 틀렸습니다 가 뜨더라구요

어디가 틀렸는지..어느부분이 ....ㅜ아마 60~66 번째 줄에서 틀렸는거 같은데 반례case를 못찾았습니다...ㅜㅜ

(처음에는 i<=n-1 을 안넣고 했었는데

인풋 케이스가

5

0 0 0 0 0

3

-5 0 5

를 해버리니 arr가 전역변수로 잡아서 0으로 초기화된 덕에 0이 50만개나 카운트 되더군요 그래서 저렇게 했는데

그다음 반례를 못찾았어요)

그리고 10815번을 다른분들이 본걸 참조하다가 2천만개가 잡힌다는 사실을 알고.....

푸니 10816번이 맞더군요.... 그래서 말인데

문제에서 주어진 메모리초과범위 안에서만 된다면 최대치 까지 잡을수 있어요?

그게 아니면 보통 한계가 어디까지 인가요....(2천만이 된다는게 충격이었습니다)

#include <stdio.h>

int n,m,arr[500000],arr1[500000];
int ind[500000],brr[500000];

void swap(int *a,int *b){
	int temp=*a; *a=*b; *b = temp;
}

void qs(int a[],int start,int end){
	int p=a[(start+end)/2],s=start,e=end;
	while(s<=e){
		while(a[s]<p) s++;
		while(a[e]>p) e--;
		if(s<=e) swap(&a[s++],&a[e--]);	
	}
	if(start<e) qs(a,start,e);
	if(s<end) qs(a,s,end);
	
}

void qs_2(int a[],int start,int end){
	int p=a[(start+end)/2],s=start,e=end;
	while(s<=e){
		while(a[s]<p) s++;
		while(a[e]>p) e--;
		if(s<=e) {
			swap(&a[s],&a[e]);	
			swap(&ind[s],&ind[e]);	
			s++;
			e--;
		}
	}
	if(start<e) qs_2(a,start,e);
	if(s<end) qs_2(a,s,end);
	
}


int main(){
	
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&arr[i]);
	
	qs(arr,0,n-1);
	
	int m;
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d",&arr1[i]);
		ind[i]=i;
	}
	qs_2(arr1,0,m-1);
	
	int j=0;
	for(int i=0;i<n;i++){
		while(arr[i]>arr1[j]) j++;
		if(arr[i]==arr1[j]){
			while(arr[i]==arr[i+1] && i<n-1){
				brr[ind[j]]++;
				i++;
				
			}
			brr[ind[j]]++;
			j++;
		}				
		
	}
	
	for(int i=0;i<m;i++)
		printf("%d ",brr[i]);
	printf("\n");
	
	
	return 0;
}

baekjoon 8년 전 0

간단하게 계산해보면 20,000,000 * 4(int 크기) /1048576 MB 입니다.

joonas 8년 전 1

잡다하네요.

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