글 읽기 - 이분탐색 질문입니다.

bqwert36 1년 전 0

답을 출력해주기 위해 result 변수를 이용했습니다. tmp는 보석을 가지는 학생 수이기 때문에 학생 수 n보다 크거나 작으면(25번째줄) 조건에 부합하므로 result를 갱신되게 해주었습니다.

근데 답을 result로 출력하면 오답이 나오고, l으로 하면 정답이 나옵니다. 혹시 이유를 알 수 있을까요?

#include <iostream>
#include <algorithm>

using namespace std;

long long n,m;
long long arr[300010];

void binarySearch(long long left, long long right){

    long long l = left, r = right;
    long long tmp = 0, mid = 0; // mid는 long long
    long long result = 10000000;

    while(l <= r){
        mid = (r + l) / 2;
        tmp = 0;

        for(int i = 0; i < m; i++){
            tmp += arr[i] / mid; // 나눈 개수를 한 명이 들고간다.
            if(arr[i] % mid != 0) // 남은 보석을 다른 한 명이 가져간다.
                tmp++;
        }

        if(tmp <= n){ // 이 부분이 답일 수도 있으나, 더 작은 수를 찾기 위함
            //result = min({result, mid}); // 해당 분기에 들어오는 마지막 값이 가장 작은 수
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    cout << l << '\n';
}


int main(){

    cin >> n >> m;

    int left = 1 ,right = 0;

    for(int i=0; i<m; i++){
        cin >> arr[i];
        if(right < arr[i])
            right = arr[i];
    }

    binarySearch(left, right);

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이분탐색 질문입니다.

bqwert36 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말