2805 나무 자르기

 

이분탐색 문제였다. 아래 링크 참고해서 개념 이해하고 풀었다. 이분탐색 전에 배운 적 있었는데 코드로는 처음 짜봐서 신기했음,,

 

http://blog.naver.com/kks227/220777333252

이분 탐색(Binary Search) (수정 2019-02-15)

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

bool cut(int mid,int m, vector<int> v){
    i64 sum = 0;
    
    for(int i = 0; i < v.size(); i++)
        sum += max(0, v[i]-mid);
    if(sum >= m)
        return true;
    else
        return false;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> v(n);
    
    for(int i = 0; i < n; i++)
        scanf("%d", &v[i]);
        
    int low = 0;
    int high = *max_element(v.begin(), v.end());
        
    while (true){
        if(low == high-1)
            break;
        int mid = (low+high)/2;
        if(cut(mid, m, v))
            low = mid;
        else
            high = mid;
    }
    
    printf("%d", low);
        
    return 0;
}

 

처음 제출했을 때 틀렸는데 알고보니 sum 구할 때 오버플로우가 발생했다. 입력 값이 커서 오버플로우 조심해야지 생각하다가 까먹고 long long 안 써서 틀렸다. 다음에는 더 조심하도록 하자.