글 읽기 - 시간초과 대체 왜걸리는지 궁금합니다. 고수님들 제발 도와주십시오 ㅠㅠ

skyeee25 1년 전 0

이진탐색 쓰라고 해서 이진탐색 썼습니다. 간간히 for 이중 중첩 코드가 생각났지만 꾸욱 참고 이중중첩을 쓰지 않았습니다. 값은 제대로 나옵니다. 선생님들 대체 어떻게 해야 시간을 줄일 수 있을까요?

import java.io.InputStreamReader;

import java.util.*;
public class Main {

	public static void main(String[] args)throws IOException {
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 String s=br.readLine();
 
 String []spt =s.split(" ");
 int a=Integer.parseInt(spt[0]);
 int []arr=new int[a];
 int n=Integer.parseInt(spt[1]);
for(int i=0;i<a;i++) {
	
	arr[i]=Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
scan(n,arr,0,arr[0]);
	
}
public static void scan(int N,int []arr,int min,int max) {
	int sum=0;
	int pivot=(min+max)/2;
	
	for(int i=0;i<arr.length;i++) {
		
		sum+=arr[i]/pivot;
		
	}
	
	if(sum==N) {
	 sum=0;
		for(int i=0;i<arr.length;i++) {
			
			sum+=arr[i]/(pivot+1);
			
		}
		
		if(sum<N) {
			System.out.println(pivot); 
		}
		else {
			min=pivot+1;
			scan(N,arr,min,max);//조건을 만족하는 값중에서 찾은 값보다 큰 값이 있으므로 더 탐색
		}
		
	}
	else if(sum<N) {
	
	max=pivot-1;
	scan( N,arr, min, max);// 조건을 만족하는 값보다 피벗 값이 크므로 피벗보다 작은 값에서 탐색
	
	}
	else {
		min=pivot+1;
		
		scan( N,arr, min, max);//조건을 만족하는 값보다 피벗값이 작으므로 피벗보다 큰 값에서 탐색
	}
	
}
	
	}

cksgud410 1년 전 1

Arrays.sort()을 진행하면 평균 시간복잡도가 O(nlog₂n)입니다.

코드를 읽어보니 Array.sort()를 하는 이유가 최대값을 구하는 것이기 때문에

Array.sort()를 사용하지 않고 입력값만 비교하여 최대값을 구하는 방향으로 진행하면 좋아질 것 같습니다.

이분 탐색은 중간값을 통해서 조건에 만족하는지 확인하여 조건에 만족하는 값을 찾는 알고리즘입니다.

42~53줄의 코드는 중간값을 이용하는 것이 아닌 추가적으로 for문을 진행하는 것으로 시간초과의 원인이 될 것 같습니다.

42 ~ 53줄 코드는 조건에 만족하는 최대 랜선의 길이를 찾아서 이분탐색을 종료하는 코드로 보입니다.

그럼.. 2.번에서 설명한 코드를 없애개 된다면 다른 방식의 이분 탐색을 종료하는 방법을 고민해서 적용시키면 시간초과가 발생하지 않을 것 같습니다.

skyeee25 1년 전 0

넵 감사합니다

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

문제

문제

출처

ICPC

시간초과 대체 왜걸리는지 궁금합니다. 고수님들 제발 도와주십시오 ㅠㅠ

skyeee25 1년 전 0

cksgud410 1년 전 1

skyeee25 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말