나무 자르기 [C++]

문제 링크: https://www.acmicpc.net/problem/2805

난이도: ⚪⚪ / SILVER2

1. 문제 설명

2. 문제 접근

• 💡 N의 범위가 1이상 1,000,000 이하의 정수이기 때문에 시간초과에 유의한다.
• 💡 이분탐색 혹은 매개 변수 탐색을 이용하여 시간복잡도를 O(log n)으로 줄일 수 있다.

1. 배열에 주어진 나무들의 길이를 입력하고 매개 변수 탐색을 하기 위해 정렬을 해준다.
2. 탐색의 시작 값과 마지막 값을 정하고 중간값을 이용해 M보다 크고 작은지를 판별한다.
3. 판별한 값이 M보다 크다면 시작 값을 늘려 판별을 진행하고,
   판별한 값이 M보다 작다면 마지막 값을 늘려 판별을 진행한다.
4. 판별한 값을 최대값으로 갱신시키며 판별을 진행한다.

3. 제출 코드

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

// 매개변수 탐색 구현
bool FindMaxHeight(long middle_value, long target, vector<long>& vec)
{
    // 가져갈 나무의 길이
	long long sum_len = 0;

	for (int i = 0; i < vec.size(); i++)
		if (vec[i] - middle_value > 0)
			sum_len += (vec[i] - middle_value);

	if (sum_len >= target)
		return true;
	else
		return false;
}

// 메인 함수
int main(void)
{
    // 빠른 입력
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	long M;
	cin >> N >> M;

    // 나무를 남을 배열 선언과 입력.
	vector<long> trees;
	long tree;
	for (int i = 0; i < N; i++)
	{
		cin >> tree;
		trees.push_back(tree);
	}
    // 매개 변수 탐색을 위한 정렬
	sort(trees.begin(), trees.end());

	long start_h = 0;           // 탐색의 시작 높이
	long end_h = trees[N - 1];  // 탐색의 마지막 높이
	long max_h = 0;             // 절단기 최대 높이

    // 시작 높이와 마지막 높이가 같아질 때 까지 반복한다.
	while (start_h <= end_h)
	{
		long mid = (start_h + end_h) / 2;   // 중간값
		
        // 만약 mid가 M보다 크다면, max_h를 갱신하고 start_h에 값을 증가시키고
        // mid가 M보다 작다면 end_h를 감소시킨다.
        if (FindMaxHeight(mid, M, trees))
		{
			max_h = max(max_h, mid);
			start_h = mid + 1;
		}
		else
			end_h = mid - 1;
	}

	cout << max_h;
	return 0;
}

4. 풀이 과정

나무의 수는 1,000,000이하이기 때문에 탐색을 진행할 때 2중 중첩문을 사용하면 시간초과가 날테니 O(n²)미만의 시간복잡도를 이용해야 겠다는 생각이 들었다.

이럴때 이진탐색을 사용하면 탐색 범위를 반씩 줄이기 때문에 탐색이 가능하다는 생각이 들었고, 가져가야 할 최소 높이 M이 주어졌기 때문에 매개 변수 탐색을 이용하면 될 것 같다고 생각했다.

// 판별 함수
bool FindMaxHeight(long middle_value, long target, vector<long>& vec)
{
    // 가져갈 나무의 길이
	long long sum_len = 0;

    // 나무를 자르고 가져갈 수 있는 나무의 총 길이를 구한다.
	for (int i = 0; i < vec.size(); i++)
		if (vec[i] - middle_value > 0)
			sum_len += (vec[i] - middle_value);

    // target(M) 보다 내가 구한 길이가 더 길다면 true, 그렇지 않다면 flase를 반환한다.
	if (sum_len >= target)
		return true;
	else
		return false;
}

// ... 중간 생략

// 탐색 부분
while (start_h <= end_h)
{
    long mid = (start_h + end_h) / 2;   // 중간값
    
    // 만약 mid가 M보다 크다면, max_h를 갱신하고 start_h에 값을 증가시키고
    // mid가 M보다 작다면 end_h를 감소시킨다.
    if (FindMaxHeight(mid, M, trees))
    {
        max_h = max(max_h, mid);
        start_h = mid + 1;
    }
    else
        end_h = mid - 1;
}

시작값과 마지막 값을 정하고 그 값들이 만날 때 까지 탐색을 진행하며, 내가 구하고자 하는 값이 M보다 크다면 시작 값을 늘려 탐색 해본다.

이렇게 탐색을 진행하면 가져갈 수 있는 나무의 길이가 M과 같거나 큰 경우, 내가 설정한 절단기의 높이를 최대로 갱신시킬 수 있다.

5. 결과