백준 : 2805 - 나무 자르기

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

 

난 이런문제를 보면 그냥 구현으로 풀었는데

(min 또는 max를 생각해서 1씩 올리거나 낮춰보기)

이진탐색으로 푸는거라고 한다!

 

전체적인 느낌은 비슷하다

(나름 생각해서) 초기값을 정하고,

테스트를 한 다음 테스트값에 따라 초기값을 늘리거나 줄이거나 해준다.

 

근데 나처럼 1씩 올려주거나, 1씩 줄여주면 너무 오랜시간이 걸릴 수 있다 (모든 경우를 탐색해야할수도 있음)

 

근데 이진탐색은?

경우의수를 계속 2로 나눠주니까.. 시간면에서 엄청난 이득을 본다! (굳이 확인 안해도 될것같은 부분은 넘기는것)

---

나무자르기 문제도 비슷하다.

 

1. 제일 긴 나무를 기준으로 min = 0, max = tree[제일 긴나무] 로 설정해준다.

 

2. mid = (min + max) / 2

    => mid를 톱 높이로 설정해서 잘라보기 (자른 나무 길이를 봐야함)

2-1. 결과가 m과 같을 때

    지금 mid가 제일 좋은상황이니까

    => break

2-2. 결과 > m

    mid가 너무 "작은"것! (너무 아래에서 잘라서, 너무많이 나무가 잘림)

    => min = mid 변경해준다

2-3. 결과 < m

    mid가 너무 "큰"것 (너무 위에서 잘라서, 너무 적게 잘라버린것)

    => max = mid 변경해준다.

3. 2번과정을 반복한다

    이 때, min +1 < max일때만 반복을 진행해준다.

    !(min+1 < max)일 때 break해주기 (반복문 탈출)

 

* 적어도 m 미터의 나무를 가져가야 한다

    == m미터보다 조금 더 많이 가져가도 괜찮음!

    == m미터보다 많이 가져가는것 중, 제일 적게 가져가는 상황을 만족해야함

 

* 반복조건

    사실 지금까지 binary search를 구현할 때, while(true)안에 따로 if문으로 탈출조건을 적어줬다.

    근데 생각해보면.....min과 max가 같아지거나, 바로 한칸차이일 때 탈출해줘야한다

    min이 max를 "초과" 하는 상황은.... 생길수가 있나?

    업데이트할 때 그냥 mid = max 혹은 mid = min 으로 작성한다면, 절대 두개가 바뀔수는 없다!

    그러면, min == max일때만 생각하면 되는가? 그건 또 아니다!

    min = 9, max = 10일 때 mid는 9가 된다 (int 나눗셈)

    즉... min이 업데이트됐을 때, min == max만 탈출조건이면 탈출을 못하고,

    max가 업데이트 되면 탈출은 하는데, 딱히 mid에 변화는 없는 상황이다

    그러니까 그냥 min + 1 == max 인 상황에도 바로 탈출시킬 수 있다!

    결론 : while(min + 1 < max) 로 작성하는 상황도 염두해두자!

 

---

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

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long n, m;
    vector<long long> trees;
    cin >> n >> m;
    long long maxvalue = 0;
    long long minvalue = 0;
    for(int i = 0; i<n; i++){
        long long temp;
        cin >> temp;
        trees.push_back(temp);
        maxvalue = max(maxvalue, temp);
    }

    long long mid;
    while(minvalue + 1 < maxvalue){
        
        mid = (maxvalue + minvalue)/2;
        long long cuts = 0;
        for(int i = 0; i<trees.size(); i++){
            if(trees[i] > mid){
                cuts += (trees[i] - mid);
            }
        }
        if(cuts > m){
            minvalue = mid;
        }else if(cuts < m){
            maxvalue = mid;
        }else{
            break;
        }
    }
    mid = (maxvalue + minvalue)/2;
    cout << mid;

    return 0;
}

---

이진탐색 관련 문제를 좀 더 풀어봐야겠다.

매번 어떻게 구현은 하는데... 세세한 부분까지 컨트롤 하지 못하는것같다.

특히 지금처럼.. 딱 그 숫자 하나를 찾는게 아니라, 어떤 범위를 만족하는 최적의 숫자를 찾을때는

종료조건도 좀 더 신경쓰고.. 그래야 할 것 같은데ㅠ 어렵구만~~

 

 

mid 업데이트 조건 (max - 1,, 이런식으로) 도 바꿔보고

종료조건도 바꿔보고... 

전부다 맞는것같은데 안된다ㅠㅠ

어렵다 어려워~~~