[백준] 나무 자르기 2805번

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

package baekjoon;

public class CuttingTree_2805 {

	private static int findHeight(int n, int m, int tree[]) {
		int ans = -1;

		int cutting[] = new int[20];

		for(int i=0; i<cutting.length; i++) {
			for(int j=0; j<tree.length; j++) {
				if(tree[j]>(i+1)){
					cutting[i] += tree[j] - (i+1);
				}
			}
			if(cutting[i]==m) {
				ans=i+1;
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		int n = 4; int m = 7;
		int tree[] = {20,15,10,17};

		int answer = findHeight(n, m, tree);
		System.out.println(answer);

		sc.close();
	}
}

처음 짰던 코드

이렇게 짠다면 이진 탐색이 의미가 있을까 생각했다. 애초에 이진 탐색이 아니라 전체 탐색임.

for문을 두 번 반복하기에 시간 복잡도도 O(n^2).

(그리고 tree에 있는 가장 큰 원소를 가져와서 cutting 배열의 수를 선언해야하는데 문제가 생김.)

 

 

그래서 생각을 해봤다.

이진 탐색은 처음과 끝에서 중간을 찾아서 탐색하는 방법이다. 

배열을 이진 탐색하는 게 아니라 절단기의 높이를 0부터 tree에서 가장 큰 높이 중간을 책정하는 이진탐색을 활용하니 금방 풀렸다.  

 

그렇다면

1. tree의 배열에서 가장 큰 원소를 먼저 찾는 클래스를 작성하고

2. 원소의 값을 리턴한 후 리턴한 값으로 이진 탐색을 하면서

3. 제시된 m미터의 나무를 가져갈 때까지 구함.

이런 결론에 이르게 되었다.

 

public class BinaryTree {

    private static int searchTree(int arr[], int key) {
        int start = 0;
        int end = arr.length-1;
        int ans = 0;

        while(start<=end) {
            int mid = (start+end)/2;

            if (arr[mid] < key) {
                start = mid;
//              System.out.println(start+", "+end);
            } else if (arr[mid] > key) {
                end = mid;
//              System.out.println(start+" "+end);
            } else {
                return mid;
            }
        }

        return -1;
// 찾는 수가 없는 경우 -1로 리턴
    }

    public static void main(String[] args) {
        int data[] = {2,3,5,8,10,15,21,26};
        int number = 21;

        int ans = searchTree(data, number);
        System.out.println(ans);
    }
}

예전에 짰던 이진 탐색 참조. (재귀와 for문 두 버전 추후 업로드 예정)

 

---

다시 참고해서 생각한 나무 자르기 해답은 다음과 같다.

package baekjoon;
import java.util.Scanner;

public class CuttingTree_2805 {
	private static int findCutting(int n, int m, int tree[]) {
		int h = findHighest(tree);
		int start = 0;
		int end = h;

		while(start<=end) {
			int mid = (start+end)/2;
			int tmp = 0;
			for(int i=0; i<tree.length; i++) {
				if(tree[i] >= mid) {
					tmp += tree[i] - mid;
				}
			}

			if(tmp>m) {
				start = mid;
			} else if(tmp<m) {
				end = mid;
			} else {
				return mid;
			}
		}

		return -1;
	}

	private static int findHighest(int tree[]) {
		int high = tree[0];
		for(int i=1; i<tree.length; i++) {
			if(high<tree[i]) {
				high = tree[i];
			}
		}
		return high;
	}



	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int tree[] = new int[n];
		for(int i=0; i<n; i++) {
			tree[i] = sc.nextInt();
		}

		int ans = findCutting(n, m, tree);
		System.out.println(ans);
	}
}

▷ 결과는 시간 초과

다시 생각을 해봤을 때 Scanner로 tree 배열에 넣을 때 가장 큰 나무의 길이를 구해도 되기 때문에 findHighest 메소드를 구현해서 for문을 또 돌릴 필요가 없다고 느꼈다.

 

package baekjoon;
import java.util.Scanner;

public class CuttingTree_2805 {
	private static int findCutting(int n, int m, int h, int tree[]) {
		int start = 0;
		int end = h;

		while(start<=end) {
			int mid = (start+end)/2;
			int tmp = 0;
			for(int i=0; i<tree.length; i++) {
				if(tree[i] >= mid) {
					tmp += tree[i] - mid;
				}
			}

			if(tmp>m) {
				start = mid + 1;
			} else if(tmp<m) {
				end = mid;
			} else {
				return mid;
			}
		}

		return -1;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int tree[] = new int[n];
		int high = tree[0];

		for(int i=0; i<n; i++) {
			tree[i] = sc.nextInt();

			if(high<tree[0]) {
				high = tree[i];
			}
		}

		int ans = findCutting(n, m, high, tree);
		System.out.println(ans);
	}
}

또 시간 초과가 나는데 왜 나는지는 잘 모르겠다. 찾아보려고 한다.