글 읽기 - 자바 고수님들 도와주세요 ㅠㅠ

tjdals333 3년 전 0

웬만한 케이스 다테스트해보고 했는데 값딱나오는데

35프로쯤가서 틀렸습니다 나와요 ㅠㅠ

어디가 틀렸는지모르겠는데 알려주시면 감사하겠습니다

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
	
	static long arr[] ;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = null;
		
		st = new StringTokenizer(bf.readLine()," ");
		int treenum = Integer.parseInt(st.nextToken());
		long treelength = Long.parseLong(st.nextToken());
		
		arr = new long[treenum];
		st = new StringTokenizer(bf.readLine()," ");
		
		for(int i=0 ; i<treenum ; i++) {
			arr[i]=Long.parseLong(st.nextToken());
		}
		
		Arrays.sort(arr); //비효율적인 알고리즘 ?
		
		System.out.println(treecut(treelength));
		
		}
	
		private static long treecut(long a) {
			int index = arr.length-1;
			long length = arr[index];
		//	int sum =0;
						
		out: while(true) {
				long sum =0;
				index = arr.length-1;
				length--;
				while(true) {
				if((sum<a) && (arr[index]-length)<=0) break;
				sum=sum+arr[index]-length;
				if(sum>=a) break out;
				index--;
				if(index==0) break;
				}	
			}
			return length;
			
			
		}
}

golazcc83 3년 전 1

47번째 줄에서 index를 1 감소시키고 index가 0인 경우 while문을 벗어나게 되어 있습니다.

이 경우 arr의 0번째 index 를 고려하지 않게 됩니다.

작성하신 코드는 나무의 최대 높이부터 0까지 1씩 감소하며 탐색하고 있습니다.

이 경우 시간 복잡도는 O(NM)이 되어 최악의 경우 1,000,000,000,000,000번의 연산을 수행해야 할 수도 있습니다.

이분 탐색에 대해 찾아보셔서 이 부분을 최적화해보시는 것을 추천드립니다.

20 1000000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1000000000

정답 : 0
작성하신 코드 : 시간 초과

tjdals333 3년 전 0

감사합니다 많은 도움이됬습니다 ^^

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

문제

문제

출처

ICPC

자바 고수님들 도와주세요 ㅠㅠ

tjdals333 3년 전 0

golazcc83 3년 전 1

tjdals333 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말