[BOJ/백준 - 2805] 나무 자르기

출처: https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

---

	public class BOJ_TEMP {
	public static void main(String[] args) throws Exception{
	// INPUT & INIT
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int a = Integer.parseInt(st.nextToken());
	int target = Integer.parseInt(st.nextToken());
	Integer[] arr = new Integer[a+1];
	st = new StringTokenizer(br.readLine());
	for(int i=0; i<arr.length-1; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
	}
	arr[arr.length-1] = 0;
	// SORT
	Arrays.sort(arr, Collections.reverseOrder());
	// CALCULATE
	long answer = 0;
	long sum = 0;
	for(int i=0; i<arr.length-1; i++) {
	long temp = arr[i] - arr[i+1];
	long tempSum = sum + (temp * (i+1));
	// 여태까지 자른 길이의 합이 딱 맞다면 다음원소의 길이를 출력하고 마무리
	if(target == tempSum) {
	answer = arr[i+1];
	break;
	}else if(target < tempSum || i==arr.length-2){
	// 길이의 합이 더 길다면 or 마지막
	long n = Math.abs(tempSum - target);
	answer = arr[i+1] + (int)(Math.ceil(n/(i+1)));
	break;
	}else { // 길이의 합이 아직 더 적다면 한번 더 잘라본다
	sum = tempSum;
	}
	}
	// OUTPUT
	System.out.println(answer);
	}
	}

view raw BOJ_2805.java hosted with ❤ by GitHub

---

주의 : 이분 탐색 아님!!! 개느림!!! (2160ms)

나는 거의 그리디? 완전탐색? 잘모르겠네.. 여튼 그런식으로 풀었음

푸는 방식은 입력을 받고 내림차순으로 정렬한다. (소스 보면 알겠지만 맨 뒤에 0이 더 있음)

 

앞에서부터 다음 원소의 높이와 같아지게 자르고 여태까지 잘랐던 나무를 더한다

그리고 그 값이 목표치와 비교해서

1. 딱 맞다면 다음 원소의 높이와 같다면 다음원소의 높이까지만 자르면되고

2. 아직 모자르다면 반복문의 다음 루프로 보낸다

3. 더 많이 잘랐거나 마지막 0과 비교할 때는

   다음원소의 값과 덜 자를만큼의 길이를 비교해서 계산한다

 

백준 input으로 예시를 들면

예시 1

4 7
20 15 10 17

정렬
20 17 15 10

계산 (실제 배열의 값은 변하지 않음)
나무의 길이    자른나무 길이의 합 :
20 17 15 10 
17 17 15 10 >  0 + (3*1) = 3  
15 15 15 10 >  3 + (2*2) = 7

예시 2

5 20
4 42 40 26 46

정렬
46 42 40 26 4

계산 (실제 배열의 값은 변하지 않음)
나무의 길이      자른나무 길이의 합
46 42 40 26 4  
42 42 40 26 4 >  0 + (4*1) = 4  
40 40 40 26 4 >  4 + (2*2) = 8
26 26 26 26 4 >  8 + (14*3) = 50

지금 30만큼 넘치게 잘랐다 
현재까지 나무는 3개를 잘랐으니 10만큼씩 덜 자르면 된다
그래서 26 + 10 = 36

이런 방식으로 자르고 특이케이스 부분들만 처리해주면된다 

5 2000000000 
900000000 900000000 900000000 900000000 900000000

이런 경우 값이 다 똑같기 때문에 마지막 원소까지 가게되었을 경우 절대값 처리를 해서 계산했다

 

일단 통과는 했는데 이분탐색으로 다시 생각하고 풀어봐야겠다