[백준] 2805번 - 나무 자르기

www.acmicpc.net

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

문제

💡

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

시간 제한: 1초

메모리 제한: 256MB

입력

💡

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

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

💡

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

예제 입력	예제 출력
4 7 20 15 10 17	15
5 20 4 42 40 26 46	36

코드


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool operation(int mid, const vector<int>& tree, int N, int M) {
	long long result = 0;
	for (int i = 0; i < N; ++i) {
		if(tree[i] >= mid)
			result += tree[i] - mid;
	}
	return result >= M;
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	vector<int> tree(N);
	for (int i = 0; i < N; ++i) {
		int T;
		cin >> T;
		tree[i] = T;
	}
	
	int left = 0;
	int right = 1e9;
	int mid;
	int answer = 0;
	while (left <= right) {
		mid = (left + right) / 2;
		if (operation(mid, tree, N, M)) {
			left = mid + 1;
			answer = mid;
		}
		else {
			right = mid - 1;
		}
	}

	cout << answer;
	return 0;
}

풀이

문제에서 최솟값을 구하라는 조건을 통해, 파라메트릭 서치 문제임을 유추할 수 있었다. 주어진 나무 높이 배열에서 특정 높이를 기준으로 잘랐을 때, 잘린 나무의 총합이 M 이상이 되는지를 판단하며, 이 조건을 만족하는 최대 높이를 찾아 출력하면 된다. 평소 자주 사용하는 파라메트릭 서치 템플릿을 그대로 적용했다.

이 유형에서 내가 자주 실수하는 부분은 이분 탐색의 최대값 설정과 조건 함수의 구현 방식이다. 이번 문제에서는 나무의 길이에서 자르려는 높이를 빼면 잘린 나무의 길이를 구할 수 있는데, 나무의 높이가 자르려는 높이보다 작으면 음수가 나올 수 있으므로, 이를 방지하기 위해 조건문으로 예외 처리를 넣었다.

또한 나무의 길이는 최대 1e9까지 주어지므로, int 자료형으로도 저장은 가능하다. 하지만 잘린 길이의 총합은 최악의 경우 1e9 * 1e6 = 1e15까지 커질 수 있으므로, result는 long long으로 선언해 오버플로우를 방지했다.

이분 탐색에서 right의 초기값은 나무의 최대 높이가 되어야 한다.

자르려는 높이가 나무의 가장 높은 값보다 크면 항상 0이 나오므로, 탐색 범위를 줄이기 위해 1e9로 설정했다.

다른 사람의 풀이를 보니, std::max_element 로 right 값을 구하는 방식이 있었다. 처음에는 가독성도 좋고 직관적으로 느껴졌지만, 곰곰이 생각해보니 std::max_element는 시간복잡도 O(n)이다. 이 문제의 경우 n이 매우 크고, 어차피 이분 탐색에서 O(log n) 스케일로 접근하기 때문에, 고정된 큰 상수로 시작하는 편이 오히려 더 효율적일 수 있다고 판단했다.

return값을 구하기 위해 long long으로 선언한 result와 int형 M을 비교할 때 형변환 규칙이 어떻게 되어있는지 궁금증이 생겼다.

조사해보니, C++에서는 산술 연산 시 자료형의 '정밀도(용량)'가 큰 쪽으로 자동 형변환이 일어난다고 한다.

즉, long long(8byte)과 int(4byte)를 연산하면 long long으로 변환된다.

한편, long long과 float 를 연산하면 정수보다 실수가 우선되기 때문에 float로 형변환되어 연산된다.

하지만 이 경우 long long보다 float가 표현할 수 있는 정수 부분의 길이가 짧아 그만큼 손실이 발생할 수 있으므로, 상황에 따라 개발자가 명시적으로 형변환을 관리해야 한다.