[Silver II] 나무 자르기 - 2805

문제 링크

성능 요약

메모리: 9832 KB, 시간: 168 ms

분류

이분 탐색, 매개 변수 탐색

🥴 Hmm...

이분탐색으로 풀면 쉽게 풀릴 거 같아서 슉슉 코드를 적고 테스트 케이스를 넣었는데
바로 맞아서 오 좋은데? 하면서 답을 넣었지만 시간초과가 났다.
흠... 모르겠는데 하다가 질문 게시판의 반례들을 집어넣으니까
어? 뭔가 알 것 같다. 일단 l 이 r보다 작을 때만 while문을 돌려줘야 한다.

흠 고쳤는데도 되지 않았다. 왜 안되지...? 또 질문게시판을 둘러보다가 깨달았다.
이 문제는 "적어도" m 크기의 나무를 가져갈 수 있다.. 였다.
그 말은, 반드시 m 크기의 나무를 가져가지 않아도 된다는 거였다.
하.. 이런게 어딨어요!!

이 부분에 대해서 좀 고쳐주니 맞았다 ㅎㅎ

🖥️ 소스코드

#define fastio ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <string.h>
using namespace std;

/* Method Initialization */
void input();
void solve();
int cal(int a, int b);
/* Variable Initialization */
int n;
long long m;
int tr;
int mx = -2e9;
long long sum;
long long a[1000004];


int main()
{
    fastio;
    solve();
    return 0;
}

void solve()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> tr;
        a[i] = tr;
        mx = max(tr, mx);
    }
    if (mx == m){
        cout << 0 << '\n';
        return;
    }
    int l = 1;
    int r = mx;
    int mid = mx/2;
    while(l <= r) {
        sum = 0;
        for (int i = 0; i < n; i++) {
            sum += cal(a[i], mid);
        }
        if (sum >= m) {
            l = mid + 1;
            mid = (r + l) / 2;
        }
        else{
            r = mid - 1;
            mid = (r + l) / 2;
        }
    }
    cout << mid << '\n';
}

int cal(int a, int b)
{
    int tmp;
    if (a - b < 0) return 0;
    return a - b;
}