[CPP] 2805 - 이진탐색 문제 풀이

✅ 문제

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

✅ 이진 탐색

이진 탐색 문제의 특징

• 이진 탐색 문제는 대부분 데이터가 굉장히 많아서, 탐색에 시간이 굉장히 오래걸릴 거 같은 느낌이 드는 문제이다.
• 이 문제 역시도 데이터(나무의 높이)가 최대 1000000000 일 수 있어, 1씩 높여가면서 탐색을 하려고 할 때 시간 초과가 날 거라는 건 쉽게 짐작할 수 있다.
• 참고로 이 자료를 저장할 수 있을 만한 자료형에 적절히 저장해야 한다. (long long 등)

이진 탐색 문제를 풀려면?

• 이진 탐색 문제에서는 정렬을 하거나, 최대 최소 값을 아는 것이 중요하다.
• 중간값을 적절히 찾아야하고, start지점과 end지점을 적절히 업데이트 해야 한다.
• 종료 조건도 중요하다. 언제까지 이 탐색을 계속할 것인가? 일반적으로 start와 end가 만나거나 역전될 때 종료한다.

내 답안 분석하기~

#include <iostream>
#include <vector>
#include <unistd.h>

using namespace std;

int main() {
    long long treeNumber, targetHeight;

    vector<long long> treeList;
    long long maxHeight = 0;


    scanf("%llu %llu", &treeNumber, &targetHeight);

    for (int i = 0; i < treeNumber; i++){
        long long height;
        scanf("%llu", &height);
        treeList.push_back(height);
        if (maxHeight < height){
            maxHeight = height;
        }
    }

    long long start = 0; // [최소 조건] 0
    long long end = maxHeight; // [최대 조건] 최대 나무 길이
    long long mid = 0;
    long long tempHeight = 1000000000;

    while (start <= end){ // [종료 조건] 
        long long currentHeight = 0;
        long long mid = (start + end ) / 2;

        for (long long i = 0; i < treeNumber; i++){
            if (treeList[i] > mid){
                currentHeight += treeList[i] - mid;
            }
        }

        if (currentHeight > targetHeight){
            start = mid+1; // [업데이트] +1
            tempHeight = mid;
        } else if (currentHeight == targetHeight){
            tempHeight = mid;
            break; 
        } else { 
            end = mid-1; // [업데이트] -1
        }
    }

    cout << tempHeight << '\n';


    return 0;
}

 

* 위의 내용은 개인 공부용으로 적어놓은 글이기 때문에 틀린 내용이 기록되어있을 수 있습니다.

* 잘못된 내용이 있을 시 피드백주시면 반영하겠습니다. :)