2805번 문제 : 나무 자르기

2805번: 나무 자르기 (acmicpc.net)

2805번: 나무 자르기

갑자기 너무 간단하게 풀었는데 시간초과가 나왔다

대충 봤었던 이분탐색을 써야할 것 같다 ..!

 

package algorithm;

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

class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		Integer arr[] = new Integer[N];
		st = new StringTokenizer(br.readLine());
		for(int i = 0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);	
		int result = 0;
		int max=0;
		for(int j=arr[0];j<arr[arr.length-1];j++) {
			int sum = 0;

			for(int i=arr.length-1;i>0;i--) {
				sum += arr[i]-j;
				
				if(sum >= M) {
					result = j;
					break;
				}
				if(result != 0) {
					if(max<result)
						max = result;
				}
			}
		}
		System.out.println(max);
	}
}

일단 처음 완성한 코드

 

이분탐색으로 저번에 했던 알고리즘이 있었던 것 같다 !

 

1654번 랜선자르기 문제에서 이진탐색을 사용했었다 (Binary search)

package algorithm;

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

class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		Integer arr[] = new Integer[N];
		st = new StringTokenizer(br.readLine());
		for(int i = 0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);	
		
		//이진탐색 !!
		long high = arr[arr.length-1];
		long low = 0;
		long max = 0;
		
		while(low<=high) {
			long mid = (high+low)/2;
			long result = 0;
			for(int i=0;i<N;i++) {
				if(arr[i]-mid > 0)
					result += (arr[i]-mid);
				}				

				if(result >= M) {
					low = mid+1;
					if(max<mid) 
						max = mid;
				}
				else if(result < M)
					high = mid -1;
			}
		System.out.println(max);
	}
}

while(low<=high) //low가 high보다 커지는 순간 탐색 종료

{

}

생각보다 간단하게 만들었는데 틀렸다고 계속 나와서 반례를 넣어봤는데

그것도 다 맞았는데 자꾸 틀렸다고 나왔다.

알고보니 자료형 문제였는데 int로 선언했던 high, low, mid, max, result를 다 long형으로 바꾸니 해결됐다.

이유가 뭘까 ?

 

int형은 4바이트로 32비트 즉 -2의 31승 ~ 2의 31승 -1 까지의 수를 표현 가능함

이걸 계산을 해보면 -21억 ~ 21억 -1 정도

근데 문제에서 상근이가 집으로 가져가려고 하는 나무 길이 M은 범위가 1부터 20억까지고

주어지는 나무의 높이들은 10억보다 작거나 같은 양의 정수 또는 0 

따라서 나무들의 높이가 저장되는 배열은 int형으로 선언해도 되지만

 필요한 나무길이 M에 따라 영향을 받는 값들은 high,low,mid,max,result들이다.

왜냐면 high는 일단 처음에 배열의 젤 끝 값으로 설정 , low는 0이고 mid 는 (high+low)/2야.

여기서 연산을 통해 나온 result값(잘라진 나무들 arr[i]-mid)이 M보다 커지 거나 작을 때까지 반복을 해야하니까

결국 result는 M이 20억언저리일 때 20억을 넘거나 M값과 같을 것이고 그렇기 때문에 int형으로는 커버불가.

result는 필수로 long이 되어야하는데

나머지 high, low, mid, max는 접점을 찾지 못 해서 int형으로 바꿔보았는데 그래도 맞았다고 떴다 !

필요한 나무길이가 M일때 내가 잘라서 더해가서 M값과 같거나 크게 만들어야할 result만 long형으로 선언하면 된다 !