백준 2805번 나무 자르기 [C/C++]

2805번: 나무 자르기

문제

나무를 필요한 만큼만 잘라서 가져감. M미터의 나무를 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최대값을 구하는 프로그램을 작성하라.

 

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

 

int형은 4바이트(32비트)이며, 수의 범위는 -2,147,483,648 ~ 2,147,483,647"이다. 즉, n(tree_num)과 m(tree_length)는 int형 범위에서 해결이 된다.

 

 그리고 mid와 같은 경우에는 start+end의 계산을 거치는데, start와 end가 int형 최대값에 가까운 숫자끼리 더해지게 되면 int형의 범위를 넘어서기에 mid는 long long타입으로 변수를 선언해준다. ( 나누기 2의 연산도 거치기에 int형으로 선언해도 테스트 케이스를 통과하지만, 혹시 몰라 long long으로 선언해주었다.)

 

 binary_search함수의 tree_length는 최대 나무 길이가 2,000,000,000인 나무들이 더해지기에 무조건 long long형으로 선언해주어야 한다.

 

int형 변수

1. main() : tree_num

2. main() : tree_length

3. main() : result

4. main() : max

 

long long형 변수

1. binary_search() : mid

2. binary_search() : tree_length

 

출력

M미터의 나무를 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int tree_len_array[1000001];

int binary_search(int start, int end, int target, int tree_num)
{
	long long mid = 0;

	// target의 길이와(7) 임의로 설정한 절단기의 높이를(cutter_high) 통해 length에 더한 값을 조건으로 사용.
	while (start <= end) {
		long long tree_length = 0; // 절단기의 높이 기준으로 잘려진 나무들의 길이 합.
		mid = (start + end) / 2;
		
		for (int i = 0; i < tree_num; i++) {
			if (mid < tree_len_array[i]) { // mid보다 작은 값인데 나무를 자르면 -값이 나옴.
				tree_length += tree_len_array[i] - mid;
			}
		}

		if (tree_length >= target) start = mid + 1; //잘려진 나무들의 길이합보다 정해진 나무들의 길이가 더 클 떄 : 절단기의 높이가 큼.
		else end = mid - 1;
	}

	return end;
}

int main()
{
	//tree_num : 나무의 수
	//tree_length : 집으러 가져가려고 하는 나무의 길이
	int tree_num, tree_length;
	cin >> tree_num >> tree_length;

	int max = 0;

	for (int i = 0; i < tree_num; i++) {
		scanf("%d", &tree_len_array[i]);
		if (max < tree_len_array[i]) max = tree_len_array[i];
	}

	int result = binary_search(1, max, tree_length, tree_num);
	printf("%d", result);
	

	return 0;
}