99클럽 코테 스터디 6일차 TIL + 이진탐색(C++)

문제

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

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

 

코드

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

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> v(N);
    
    for (int i = 0; i < N; i++)
        cin >> v[i];
    
    sort(v.begin(), v.end());
    
    int left = 0;
    int right = v.back();
    int ans = 0;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        long long sum = 0;
        
        for (int tree : v)
            if (tree > mid)
                sum += (tree - mid);
        
        if (sum >= M) {
            ans = mid;  // 가능한 높이 저장
            left = mid + 1; // 더 높은 값 탐색
        } else {
            right = mid - 1; // 더 낮은 값 탐색
        }
    }
    
    cout << ans;
    
    return 0;
}

 

풀이

주어진 나무의 높이에서 잘라낼 수 있는 최대 높이를 찾는 문제이다.

만약 단순히 가장 높은 나무 길이에서 1씩 감소시켜가며 잘린 나무 길이의 합과 M을 비교하는 식으로 코드를 작성한다면 시간 초과가 발생할 수 있다.

이렇게 특정 조건에서 최댓값 또는 최솟값을 찾아야할 때는 이진탐색을 사용하는 게 효율적이다.

 

이진탐색 과정

1. left, right 초기 설정

이진탐색시 left는 절단기 높이의 최솟값인 0으로, right는 절단기 높이의 최댓값으로 설정한다.

 

2. mid, sum 계산

중간값 mid를 계산한 후, 나무 높이가 저장된 벡터를 순회하며 나무 높이가 mid보다 클 경우에만 나무 높이에서 mid를 빼고 그 결과를 sum에 더한다. sum은 잘라낸 나무의 길이의 합을 의미한다.

 

3. 조건에 따른 탐색 범위 수정

• sum >= M: 필요한 것보다 더 많이 잘렸다는 뜻이므로, 절단기 높이를 올리기 위해 ans에 left를 저장하고, left를 mid + 1로 업데이트한다.
• sum < M: 필요한 것보다 덜 잘렸다는 뜻이므로, 절단기 높이를 낮추기 위해 right를 mid - 1로 업데이트한다.

 

이 과정을 통해 절단기 높이의 최댓값을 ans에 저장하게 되며, 최종적으로 ans를 반환하여 문제를 해결한다.

 

주의할 점

처음에 이 문제를 풀 때 left를 sum >= M일 때 증가시켜야 하는지 sum < M일 때 증가시켜야 하는지 헷갈렸다.

이에 대해 지피티선생님께 물어봤더니 명쾌히 답을 알려주셨다.

이진 탐색에서 대소비교를 어떻게 설정할지는 문제의 목표와 기준 조건을 명확히 이해하는 게 중요하다!!

이 문제의 경우, 잘라진 나무 높이의 합인 sum이 M 이상이면 조건을 만족하는 것이고 그렇지 않으면 부족한 것이다.

따라서 sum >= M 이라는 조건을 만족하는 경우에 절단기 높이의 최댓값을 찾는 게 목표이므로, 이때 left를 증가시키고 ans에 현재의 mid를 업데이트해야 한다.

 

회고

이진탐색 문제에 조금씩 감이 잡혀가는 것 같다. 확실히 같은 유형 문제를 연달아서 풀어보는 게 도움이 되는 것 같다!

 

유사한 문제

[백준] 2512번: 예산

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